프로그래머스 Java Lv2 구명 보트

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

프로그래머스

 

이번 문제는 PriorityQueue를 이용하여 해결하였다.

PriorityQueue에 값을 한번 넣을 때 마다 하나의 구명 보트가 추가 된다고 생각하였다.

이 때, PriorityQueue에 저장되는 값은 1명의 인원이 구명 보트에 타고 남은 무게 제한(kg) 이다.

*PriorityQueue - 이하 PQ

 

전체적인 흐름은 다음과 같다.

우선, 사람들의 몸무게를 담은 배열을 오름차순으로 정렬하였다. 정렬되어 있는 배열을 순차적으로 돌면서

 

1-1) PQ 에 값이 없는 경우, "무게 제한(limit) - 이번 사람의 무게"를 PQ 에 저장한다.

현재 사람이 탑승 중인 구명 보트가 없다. 그러므로 새로운 구명 보트가 추가되며, PQ 에는 남은 무게 제한이 저장된다.

 

1-2) 이 때, 남은 무게 제한이 40kg 미만인 경우 PQ 에는 값을 저장하지 않는다.

각 사람의 몸무게는 40kg 이상이므로, 남은 무게 제한이 40kg 미만이라면 더 이상 탑승할 수 없기 때문이다.

 

2) PQ 값이 있고, 남은 무게 제한이 이번 사람의 무게 이상인 경우 PQ  에서 값을 하나 제거한다.

현재 사람이 탑승 중인 구명 보트에 추가적으로 사람이 탑승하여 2명이 되었다.

무게 제한이 남았더라도 2명의 사람이 탑승하였기 때문에, 더 이상 탑승이 불가능하므로 PQ 값을 제거한다.

 

3) PQ 값이 있지만, 남은 무게 제한이 이번 사람의 무게 미만인 경우 "무게 제한(limit) - 이번 사람의 무게" PQ 에 저장한다.

가장 많은 무게 제한이 남은 보트에도 사람이 추가로 탑승하는 것이 불가하였다.

즉, 하나의 구명 보트가 더 필요하므로 PQ에 값을 저장한다.

 

 

 

코드

import java.util.PriorityQueue;
import java.util.Arrays;
import java.util.Collections;

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

        Integer[] sortedPeople = new Integer[people.length];
        for (int i = 0; i < people.length; i++)
            sortedPeople[i] = people[i];
        Arrays.sort(sortedPeople, Collections.reverseOrder());

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int person : sortedPeople) {

            if (pq.isEmpty()) {
                if ((limit - person) >= 40)
                    pq.add(limit - person);
                answer++;
            } else {

                if (pq.peek() >= person) {
                    pq.poll();
                } else {
                    if ((limit - person) >= 40)
                        pq.add(limit - person);
                    answer++;
                }
            }
        }
        return answer;
    }
}