<실패>[프로그래머스] Lv2 구명보트 / JAVA

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

프로그래머스

---

코드

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        /*
        people을 내림차순 정리한다 -> quick sort 이므로 O(nlogn)
        최댓값부터 limit 만족하는 두가지 골라본다.
        $ 효율성 테스트가 통과될까 궁금하다.
        */
        
        /*
        첫 풀이 : 테스트 실패, 효율성 시간초과, 시간 25분
        */
        int answer = 0;
        
        Integer[] arr = Arrays.stream(people).boxed().toArray(Integer[]::new);
        Arrays.sort(arr, Collections.reverseOrder());
        ArrayList<Integer> list = new ArrayList<>();
        for(int item : arr){
            list.add(item);
        }
        
        label: while(list.size()>0){
            for(int i=0; i<list.size(); i++){
                for(int j=i+1; j<list.size(); j++){
                    if(list.get(i)+list.get(j)<=limit){
                        answer++;
                        list.remove(i);
                        list.remove(j);
                        continue label;
                    }
                }
                answer++;
                list.remove(i);
                continue label;
            }
        }
        return answer;
        
    }
}

 

다른 분들의 풀이

우선 나의 논리가 틀렸다기 보다는 최적이 아니었다.

나는 가장 큰 값을 먼저 찾고, 더했을 때 limit 을 만족하는 다음 큰 값을 찾아 더해서 구명보트에 실어보내는 방식을 생각했다.

왜냐하면 가능하면 작은 값이 남아있을 수록 유리할 것으로 생각했기 때문이다.

 

하지만 다른 분들의 풀이를 보면 가장 큰 값과 가장 작은 값을 먼저 구명보트에 실어보내는 방식이었다.

처음엔 이해가 되지 않아 반례를 생각해보았는데,

 

예를들어 limit = 120kg , people[]=[90,80,70,30,20,10] 으로 가정하자.

나의 방식대로라면 90+30, 80+20, 70+10 이렇게 3개의 구명보트가 필요할 것이다.

하지만 다른 분들의 방식이라면 90+10, 80+20, 70+30 으로 마찬가지로 3개의 구명보트가 필요하다.

 

나의 방식대로 했을 때, 첫 두 값인 90+30 이후에 항상 두 값보다 더 작은 값만이 남게 되므로, 항상 limit 보다 작음을 보장할 수 있다.

즉, 음수가 아닌 자연수 배열일 때 다른 분들의 방식과 내 방식이 결국 같은 결과를 내놓게 된다.

그리고 최솟값을 뒤에서부터 찾으면 되니까 최댓값부터 찾는 나의 방식보다 비교 횟수도 줄어든다.

public class Solution {

  public int solution(int[] people, int limit) {
    int answer = 0;

    Arrays.sort(people);

    int min = 0;

    for (int max = people.length - 1; min <= max; max--){
      if (people[min] + people[max] <= limit) min++;
      answer++;
    }

    return answer;
}