[알고리즘] 프로그래머스 구명보트 -그리디(Greedy)-

 

 

https://programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

 

 

 

 

 

구명보트 그리디 유형의 문제를 풀어봤습니다.

문제의 핵심은 최대 2명이 탈 수 있다는 것입니다.

그리고 최대 2명이라는 조건이 있으니 가장 효율적으로 타는 조건은 가장 무거운 사람과 가장 가벼운 사람이 타게 하는 것입니다. 

저는 리스트를 좋아해서 처음에 리스트로 변환해서 풀었는데 밑과 같이 하나에서 시간초과가 떴씁니다. ;;;  리스트 말고 배열로  풀라는 말이겠죠..

 

 

import java.util.Collections;
import java.util.LinkedList;

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(new int[]{70, 80, 50}, 100);
    }
    public int solution(int[] people, int limit) {
        int answer = 0;
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int a : people) {
            linkedList.add(a);
        }
        Collections.sort(linkedList);
        while (linkedList.size() >= 1) {
            if (linkedList.size() >= 2) {
                if(linkedList.getLast() + linkedList.getFirst() <= limit){
                    linkedList.removeFirst();
                }
                linkedList.removeLast();
                answer++;
            }else {
                answer++;
                linkedList.removeLast();
            }
        }
        System.out.println(answer);
        return answer;
    }
}

 

 

 

위 리스트를 사용해서 시간초과 난 것을

다음과 같이 똑같은 로직으로 배열로 바꿧더니 해결되었습니다.

import java.util.Arrays;

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(new int[]{70, 80, 50}, 100);
    }

    public int solution(int[] people, int limit) {
        int answer = 0;
        int firstIndex = 0;
        int lastIndex = people.length - 1;
        Arrays.sort(people);
        while (lastIndex  - firstIndex >= 0){
            if(lastIndex - firstIndex >= 1){
                if(people[lastIndex] + people[firstIndex] <= limit){
                    firstIndex++;
                }
                lastIndex--;
                answer++;
            }else {
                answer++;
                lastIndex--;
            }
        }
        System.out.println(answer);
        return answer;
    }
}

 

 

 

 

다른 분의 블로그를 보니 코드가 깔끔해서 참고합니다. 

 

출처: https://taesan94.tistory.com/59

if(i==j) 조건의 경우 마지막에 하나가 처리못된 경우에 대한 처리입니다.

5 10, 12 ,15 20   |    25

20 5 -> i=1, j=3

15, 10 -> i=2 , j = 2

while(i>j) 조건에 의하여 하나남은 12처리못함

 

 

댓글과 공감은 큰 힘이됩니다.