[BaekJoon] 1781 컵라면 (Java)

1.  문제 링크

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

2.  문제

요약

• 상욱 조교는 동호에게 N개의 문제를 주고, 각각의 문제를 풀었을 때 컵라면 몇 개를 줄 것인지 제시하였는데, 각각의 문제에 대해 데드라인을 설정하였습니다.
• 문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N 이하의 자연수입니다.
• 동호가 받을 수 있는 최대 컵라면 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 200,000보다 작거나 같은 숙제의 개수 N이 주어지고 두 번째 줄부터 N개의 줄에 각 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 주어집니다.
  • 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수 모두 $2^{32}$보다 작거나 같은 자연수입니다.
• 출력: 첫 번째 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static PriorityQueue<Problem> problems;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        problems = new PriorityQueue<>();

        for (int problem = 0; problem < N; problem++) {
            int deadline = scanner.nextInt(), cupNum = scanner.nextInt();
            problems.offer(new Problem(deadline, cupNum));
        }
    }

    static void solution() {
        PriorityQueue<Integer> answerList = new PriorityQueue<>();

        for(int idx = 0; idx < N; idx++) {
            Problem cur = problems.poll();
            answerList.add(cur.cupNum);

            if(cur.deadline < answerList.size()) {
                answerList.poll();
            }
        }

        int answer = 0;
        while(!answerList.isEmpty()) {
            answer += answerList.poll();
        }

        System.out.println(answer);
    }

    static class Problem implements Comparable<Problem> {
        int deadline, cupNum;

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

        @Override
        public int compareTo(Problem p) {
            if(deadline != p.deadline) return deadline - p.deadline;
            return p.cupNum - cupNum;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 각 문제를 정의하는 Problem 클래스를 정의합니다.
  • 각 문제의 데드라인을 나타내는 deadline, 각 문제를 풀었을 때 얻는 컵라면 개수를 나타내는 cupNum을 멤버로 갖습니다.
  • Comparable 클래스를 구현하여 비교 시에 우선순위를 데드라인이 적게 남은 순으로, 데드라인이 같다면 얻을 수 있는 컵라면 개수가 많은 순으로 설정합니다.
• 주어진 문제에 대한 정보들을 Problem 객체로 만들어 problems라는 우선순위 큐에 넣습니다.
• problems에서 Problem 객체를 하나씩 꺼내서 해당 Problem 객체의 cupNum의 값을 새로운 우선순위 큐인 answerList에 넣습니다.
• 만약 problems에서 꺼낸 Problem 객체의 deadline이 answerList에 있는 정수의 개수보다 작다면 answerList 안에 있는 정수의 개수가 problems에서 꺼낸 Problem 객체의 deadline과 같아질 때까지 answerList에서 정수를 꺼냅니다.
  • deadline에 대해 오름차순으로 정렬하였고 한 문제를 푸는데 단위시간 1이 필요하기 때문에 현재 problems에서 꺼낸 Problem 객체의 deadline보다 더 많은 문제를 풀 수 없습니다. 그렇기 때문에 answerList에서 정수를 꺼냅니다.
  • 또한, answerList에는 각 문제를 풀어 얻을 수 있는 컵라면의 개수가 오름차순으로 정렬되어 들어있기 때문에 answerList에서 정수를 꺼낼 때 얻을 수 있는 컵라면의 개수가 적은 것부터 꺼내져 이를 통해 얻을 수 있는 컵라면 개수의 최댓값을 구할 수 있습니다.
• problems의 모든 Problem 객체에 대해 위 작업들을 완료했다면 answerList에 있는 정수들을 더합니다. 이 값이 얻을 수 있는 컵라면 개수의 최댓값이 됩니다.