구명보트

문제정의

---

최대 2명까지 탈 수 있고 무게 제한이 limit인 구명보트를 최대한 적게 사용해서 사람들을 보트에 태우는 문제이다.

문제풀이

---

전체 코드는 다음과 같다.

package level2;

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

public class LifeBoat {

    //프로그래머스 문제풀이 level2 구명보트
    public static void main(String[] args) {
        int[] people = {70, 50, 80, 50};
        int limit = 100;
        int answer = 0;
        PriorityQueue<Integer> small = new PriorityQueue<>();
        PriorityQueue<Integer> big = new PriorityQueue<>(Collections.reverseOrder());
        for(int w : people)
        {
            if(w <= limit/2)
                small.add(w);
            else
                big.add(w);
        }
        while((!small.isEmpty()) && (!big.isEmpty()))
        {
            int s = small.peek();
            int b = big.peek();
            if(s+b > limit)
            {
                big.remove();
                answer++;
            }
            else
            {
                small.remove();
                big.remove();
                answer++;
            }
        }
        if(!small.isEmpty())
            answer += small.size() % 2 == 0 ? small.size()/2 : small.size()/2+1;
        else
            answer += big.size();

        System.out.println(answer);
    }
    
}

정렬을 사용할 수 있고 우선순위큐를 활용할 수도 있지만, 필자는 우선순위 큐를 활용하였다. 15-21번째 줄은 limit/2를 기준으로 작은것과 큰 것으로 무게를 나눠담는 과정이다. small은 오름차순으로 정렬하고 big은 내림차순으로 정렬한다. 22-37번째 줄은 두 큐에서 사람을 하나씩 뽑아 보트에 태울 수 있는지 보는것이다. 만약 태우지 못한다면 큰 사람 하나를 보트에 태워보내고, 다음으로 무거운 사람을 같이 태울 수 있는지 비교한다. 만약 같이 탈 수 있으면 둘 다 큐에서 제거하고 answer를 1증가한다. 반복문을 탈출하는 경우는 두 큐 모두 비었거나, 둘 중 하나만 빈 것이므로 이에 대한 나머지 처리도 해야한다. 만약 small이 남은 경우 무조건 둘씩 태워 보낼 수 있으므로 (small 총 개수)/2를 한다. 이때 홀수명이 남는다면 1을 추가하는 것을 잊지말자. big에 속한 사람들은 한 사람씩 밖에 못 타므로 사람수만큼 추가해주면 된다.

우선 순위 큐를 활용했으므로 총 시간복잡도는 $O(nlogn)$이 된다.

테스트

처음에 40번째 줄에 else가 아니라 else if문을 썼는데 효율성 테스트를 하나 통과하지 못했다. 그래서 else로 바꾸니 통과가 되었다. size를 한번 더 호출하냐 마냐가 차이인 것 같은데, 효율성 테스트가 조금 빡빡하단 생각이 들었다.