프로그래머스 - 구명보트

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

프로그래머스

 

문제 이해가 어렵진 않았으나 시간초과를 극복하는게 중요했던 문제이다.

 

문제를 보고 오름차순 정렬 후 무게가 적은 사람과 무게가 큰 사람을 같이 태워야 보트를 최소한으로 사용할 수 있겠다고 생각했다.

 

<처음 작성했던 코드>

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        boolean[] boarding = new boolean[people.length];
        
        for(int i=0; i<people.length; i++){
            if(boarding[i]){
                continue;
            }
            for(int j=people.length-1; j>=i; j--){
                if(j==i){
                    answer++;
                    boarding[i]=true;
                }
                else if(people[i]+people[j]<=limit){
                    if(!boarding[j]){
                        answer++;
                        boarding[j]=true;
                        j=-1;
                    }
                }
                
            }
        }
        return answer;
    }
}

 

정확성 테스트는 모두 통과 했으나 효율성 테스트에서 모두 시간초과가 발생했다.

 

왜냐하면 불필요한 비교횟수가 많았기 때문이다.

 

만약 people이 [50 50 70 80] 이고, limit가 100일때

 

위 코드는 첫번째 50과 같이 탑승할 사람을 찾기 위해서 80부터 50까지 내려온다.

 

여기서 생각을 잘 해보면 50은 몸무게가 가장 적은 사람인데, 80이 몸무게가 가장 적은 사람과 탑승이 불가하다면 그 뒤는 비교 할 것도 없이 80은 혼자 탑승해야된다는게 정해진다. 

따라서 80은 다음 비교에서 제외해도 된다.

 

이걸 구현하기 위해서 left와 right를 이용해서 배열을 순회하며 비교횟수를 줄일 수 있었다.

 

 

<정답코드>

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        int left=0;
        int right = people.length-1;
        
        while(right>=left){
            if(people[left] + people[right]>limit){
                right--;
                answer++;
            }
            else{
                answer++;
                right--;
                left++;
            }
        }
        return answer;
    }
}