1781 컵라면 JAVA

컵라면

시간 제한    메모리 제한    제출    정답    맞힌 사람    정답 비율
2 초    256 MB    9153    2702    2028    30.990%

문제

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.

문제 번호 1 2 3 4 5 6 7
데드라인 1 1 3 3 2 2 6
컵라면 수 6 7 2 1 4 5 1
위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.

문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.

문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231보다 작거나 같은 자연수이다.

입력

첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

출력

첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.

풀이

문제의 핵심은 데드라인을 완수하며 문제를 풀었을 때 얻을 수 있는 최대 컵라면의 수이다.
핵심은 데드라인이 작은 순, 데드라인이 같다면 컵라면이 많은 순으로 줄세운 후 한 문제씩 택하는 것이다.
그러나 주의할 점은 데드라인이 작은 것을 택하는 것보다 데드라인이 큰 문제를 택할 때 컵라면의 수가 더 많을 수 있다는 점이다.
그래서 나는 다음과 같이 문제를 해결하였다.

1. 문제 큐(데드라인, 컵라면 수로 정렬), 정답 큐(컵라면 수로 정렬)
2. 문제를 풀 때마다 시간을 1초씩 증가시킴
   3-1. 문제 큐에서 꺼냇을 때 시간이 데드라인보다 작다면 해당 문제를 푼 문제에 넣음
   3-2. 문제 큐에서 꺼냇을 때 시간이 데드라인과 같다면 정답 큐에서 가장 작은 값과 비교하여 문제의 컵라면 값이 크다면 바꿔치기함

코드

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

public class Main {

    public static class Question implements Comparable<Question> {

        int deadLine;
        long lamen;

        public Question(int deadLine, int lamen) {
            this.deadLine = deadLine;
            this.lamen = lamen;
        }

        @Override
        public int compareTo(Question o) {
            return this.deadLine == o.deadLine
                    ? lamenCompare(o)
                    : this.deadLine - o.deadLine;
        }

        @Override
        public String toString() {
            return "Question{" +
                    "deadLine=" + deadLine +
                    ", lamen=" + lamen +
                    '}';
        }

        private int lamenCompare(Question o) {
            if (o.lamen > this.lamen) {
                return 1;
            }
            return 0;
        }
    }

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

        PriorityQueue<Question> pq = new PriorityQueue<>();

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

            pq.add(new Question(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        PriorityQueue<Long> lamens = new PriorityQueue<>();
        int time = 0;

        while (!pq.isEmpty()) {
            Question question = pq.poll();
            if (question.deadLine > time) {
                lamens.add(question.lamen);
                time++;
            } else if (question.deadLine == time) {
                if (lamens.peek() < question.lamen) {
                    lamens.poll();
                    lamens.add(question.lamen);
                }
            }
        }

        long ans = 0;
        for (Long lamen : lamens) {
            ans += lamen;
        }
        System.out.println(ans);

    }
}