백준 1781번 - 컵라면

문제

https://www.acmicpc.net/problem/1781

리뷰

우선순위큐를 활용하여 가장 많은 컵라면 수를 받을 수 있는 문제의
조합 경우를 구하는 문제였다. 최소, 최대 경우를 제한된 시간안에 도출해야
한다는 점에서 우선순위큐를 활용해야 한다는 점은 캐치하였으나
1. 데드라인이 남았을때 그냥 넘어가는 경우
2. 더 긴 데드라인을 가지는 문제가 더 큰 컵라면 개수를 가지는 경우
이렇게 두 경우를 올바르게 처리하지 못하여 애를 먹었다.

위 두 경우를 처리하기 위해 일단 문제 정보(데드라인, 컵라면 개수)를 저장하는
Problem 클래스를 산정하고, 데드라인을 기준으로 하는 최소힙을 정의하여
입력을 저장하였다.
이후 컵라면 개수를 저장하는 최소힙을 정의하였는데, 이 힙의 사이즈는 현재까지
푼 것으로 가정한 문제 수와 동일하다. 따라서, 현재 문제의 데드라인보다 푼 문제수가
작을 경우 그 문제를 일단 풀고, 이외 경우에는 가장 작은 컵라면 수와 현재 문제의
컵라면 수를 비교하여 더 높은 것을 채택하는 방식으로 코드를 구성하였다.
입력값을 데드라인 기준으로 최소힙에 저장하고 값을 꺼내어 비교하여
데드라인과 관련된 이슈가 발생하는 것을 방지하였다.

문제의 제한 조건인 $N=200,000$ 일 때 전체 로직의 시간 복잡도는
모든 값을 탐색하는 $N$과 힙에서 삽입, 삭제 연산시의 $\log N$ 을 종합한
$O(N\log N)$으로 수렴하기 때문에, 시간 제한 조건인 2초(2억 연산)을
무난히 통과한다.

참고
해당 문제의 예외 케이스를 잘 정리해두신 글을 참고하여 풀이했습니다.
https://77dptjd.tistory.com/19

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.*;

public class Main {
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N= parseInt(br.readLine());

        /**
         * pq1은 문제의 데드라인을 기준으로 하는 최소힙
         */
        PriorityQueue<Problem> pq1=
                new PriorityQueue<>(Comparator.comparingInt(p->p.deadline));
        StringTokenizer st;

        for(int i=0; i<N; i++){
            st=new StringTokenizer(br.readLine());

            int deadline=parseInt(st.nextToken());
            int reward=parseInt(st.nextToken());
            pq1.offer(new Problem(deadline, reward));
        }

        /**
         * pq2는 문제의 컵라면 개수를 기준으로 하는 최소힙
         */
        PriorityQueue<Integer> pq2 = new PriorityQueue<>();

        /**
         * 현재까지 푼 문제수(pq2.size)가 현재 문제의 데드라인보다 작을 경우
         * 푼 문제로 간주한다.
         * 이외의 경우 푼 문제들의 컵라면 수 중 가장 작은 컵라면 수(pq2.peek)를
         * 현재 컵라면 수와 비교하고, 가장 작은 컵라면 수가 더 작을 경우
         * 해당 요소를 제외하고(poll) 현재 문제를 채택한다.
         */
        while(!pq1.isEmpty()){
            Problem p = pq1.poll();

            if(pq2.size()<p.deadline)
                pq2.offer(p.reward);
            else{
                if(pq2.peek()<p.reward){
                    pq2.poll();
                    pq2.offer(p.reward);
                }
            }
        }

        /**
         * 도출된 최적의 경우, 컵라면 수들의 합을 구한다.
         * 컵라면 수의 최대값 조건이 Integer 타입을 벗어날 수 있음에 
         * 유의해야 한다.
         * 유연한 타입 대응을 위하여 var를 활용하였다.
         */
        var sum=pq2.stream().reduce((r1,r2)->r1+r2).get();
        System.out.println(sum);
        br.close();
    }

    static class Problem{
        int deadline, reward;

        public Problem(int deadline, int reward) {
            this.deadline = deadline;
            this.reward = reward;
        }
    }
}

결과