P42885. 구명보트

문제

제출 코드

• 사용 알고리즘 : 그리디, 우선순위 큐

그리디 알고리즘으로 푸는 문제임을 알고 시작했음에도, 바로 문제풀이 원리를 떠올리지 못했다.

우선순위 큐에 띄운 구명보트들의 남은 무게들을 담는다고 생각하고, 주어진 사람들을 가장 무거운 사람부터 넣기 시작한다.

사용한 구명보트 중 남은 무게가 가장 큰 구명보트와 비교해서,

1. 이번에 태울 사람이 탈수 없다면 그 사람을 태운 구명보트를 추가하고
2. 태울수 있다면 그 구명보트에 태운다

는 원리로 문제를 풀면 된다.

사실 문제를 풀면서도 예외는 없는지 확신하지 못하고 풀었다. 이게맞나..?하며 감으로 푼 셈

문제에서 한번에 최대 2명만 탈 수 있다 했으니, 큐에 담긴 보트를 꺼내 한명을 더 태울 땐, poll만 하고 다시 add하지 않도록 하자,,

문제 잘못읽어서 초반에 인원수 상관없이 태웠다..

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(Collections.reverseOrder());

        Arrays.sort(people);
        int answer = 0;

        for(int p=people.length-1; p>=0; p--){
            if(queue.isEmpty() || queue.peek()<people[p]) queue.add(limit-people[p]);
            else {
                answer++;
                queue.poll();
            }
        }

        return answer + queue.size();
    }
}