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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42885?language=java 

프로그래머스

최소한의 개수로 사람들을 보트에 다 태우자. 

 

필요한 개념

• 투 포인터 

풀이

풀이는 다음과 같다.

1. 양 끝에 있는 사람 몸무게의 합이 limt 이하이면 두 사람 모두 태운다.
2. 그 이외에는 몸무게가 큰 right 를 먼저 태운다. 
3. 정답을 리턴한다.

왜 투 포인터 인가?

주어진 조건을 보면  구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고

라 적혀있다. 오름차순으로 정렬된 배열이 있을 때 극단적인 경우의 수를 생각해 보자. 

• 몸무게가 작은 두 명을 태우는 것
• 몸무게가 큰 두 명을 태우는 것
• 몸무게가 큰 사람, 작은 사람 한 명씩 태우는 것

이렇게 3 가지가 있다. 그리디적인 측면에서 봤을때 부분적인 최적해는 3번째 큰거 하나 작은거 하나 씩 태우는 것이

아직 보트에 타지 않은 사람 총 몸무게가 가장 많이 줄어든다. 그래서 나중에는 무조건 2명씩 태울 수 있을 것이다. 

 

그러면 2명을 못 태울 경우는 당연히 몸무게가 큰 사람을 태워야 보트 안탄 총 몸무게가 가장 많이 줄어든다. 

 

코드

자바

import java.util.*;

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