[Java] 프로그래머스 구명보트

우선 그리디를 이용해서 풀어야 하는데 테스트 케이스는 전부 맞았으나 자꾸 시간초과가 났다.

 

처음 실패한 코드를 알아보자.

 

시간초과난 코드 

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < people.length; i++) {
            list.add(people[i]);
        }
        Collections.sort(list, Collections.reverseOrder());
        while(!list.isEmpty()) {
            int top = list.remove(0);
            int diff = limit - top;
            for(int i = list.size() -1; i >= 0; i--) {
                if(diff >= list.get(i)) {
                    int target = list.get(i);
                    diff -= target;
                    list.remove(i);
                } else {
                    break;
                }
            }
            answer++;
        }
        return answer;
    }
}

arrayList에 다 때려 박고 내림차순으로 정렬했다.

 

그다음 가장 끝에서 부터 하나씩 비교하면서 limit를 넘지 않는경우 arrayList에서 제거해주었고

 

arrayList의 size가 0이 될때 까지 검사했다.

 

결과는 시간초과.

 

 

 

그런데 자세히 보면 answer가 구명보트의 갯수이지, 뭐 보트를 같이 탄 몸무게를 출력하라 뭐 이런말이 없다. 즉 list에서 빼고 넣고를 하지 않아도 된다는뜻.

 

개선된 코드 

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        int idx = 0;
        for(int i = people.length -1;  idx <= i; i--) {
            if(people[idx] + people[i] <= limit) {
                idx++;
            }
            answer++;
        }
        return answer;
    }
}

 

보면 가장 끝에부터 비교한다는 것은 동일하다. 허나 list에서 따로 넣거나 뺴주는 작업 없이 idx하나로 왔다 갔다 이동한다.

 

문제에서 요구한 것을 잘 생각해보고 꼭 필요한 부분만 구현해야 효율성 테스트에서 통과 할 수 있을것 같다.

 

앞으로 문제를 풀때 고민해가면서 꼭 필요한것인가 생각하며 풀어야겠다.