[프로그래머스 알고리즘 고득점 Kit][그리디][Java] 구명보트

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

프로그래머스

 

사람들의 몸무게를 오름차순으로 정렬하고, 가장 가벼운 사람과 가장 무거운 사람을 비교한다.

• 두 사람의 무게 합이 제한을 초과하면 가장 무거운 사람만 태운다.
• 제한 이하라면 두 사람을 함께 태운다.
• 구조한 사람의 수가 전체 인원과 같아질 때까지 반복한다.

가장 무거운 사람이 가장 가벼운 사람과도 함께 탈 수 없다면 누구와도 함께 탈 수 없으므로 혼자 태워도 된다.

 

※ 마지막 한 명이 남으면 동일한 인덱스의 무게를 두 번 더하게 되지만, 보트 수는 정확히 한 번 증가하고 반복문이 종료되므로 결과에는 영향을 주지 않는다.

• 정렬: O(N log N)
• 두 포인터 탐색: O(N)
• 전체 시간복잡도: O(N log N)

 

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        
        int peopleCnt = people.length;
        int rescuedCnt = 0;
        int moveCnt = 0;
        int lightWeightIdx = 0;
        int heavyWeightIdx = peopleCnt - 1;
        
        while(rescuedCnt < peopleCnt) {
            int sum = people[lightWeightIdx] + people[heavyWeightIdx];
            if(sum > limit) {
                heavyWeightIdx -= 1;
                moveCnt += 1;
                rescuedCnt += 1;
            } else {
                lightWeightIdx += 1;
                heavyWeightIdx -= 1;
                moveCnt += 1;
                rescuedCnt += 2;
            }
        }
        
        return moveCnt;
    }
}