[백준] 13904: 과제 JAVA

접근

처음에 접근을 잘못해서 시간을 많이 써버렸는데, 다른 솔루션을 통해 과제 마감일이 늦은 기준으로 정렬하면 더 편하다는 점을 참고했다. 풀이 방법을 설명하기에 앞서, 나는 두 개의 우선순위 큐를 사용했지만 다른 분들의 솔루션을 참고해보면 N 크기를 가지는 일차원 배열을 선언하여 과제별로 각각의 값을 비교해준 것 같다. 아마 O(N^2)의 시간복잡도가 나올 것 같은데, N의 최댓값이 작기 때문에 후자의 방식이 실행 시간이 더 빠른 것 같다. 그 중 92ms의 속도가 나온 결과가 있어 눈에 띄었다.

 

우선 과제 정보를 저장하기 위해 Task라는 클래스를 선언했고, 과제 마감일을 기준으로 정렬하며 우선순위 큐에 저장했다. 이후 날짜를 하루씩 줄여가며 큐에 저장된 데이터의 마감일과 비교하며, 해당 날짜에 수행 가능한 과제들 중 점수가 가장 높은 것을 수행한다. 이때 나는 점수가 큰 순서대로 정렬하는 우선순위큐를 하나 더 선언하여, 현재 작업 가능한 과제들을 또 넣어주었다. 

 

이렇게 풀기 위해서는 Task라는 동일한 클래스에 대해 두 가지 방식으로 정렬해야 했는데, 기존에 사용하던 compareTo 함수를 오버라이딩하는 방식으로는 불가능했다. 이를 위해서 처음으로 람다식을 사용해봤다.

 

마지막으로 도움받았던 질문 게시판의 반례 링크를 함께 첨부한다. 

 

코드

package week10;

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

public class BJ13904 {
    static class Task{
        int dDay, score;

        public Task(int dDay, int score) {
            this.dDay = dDay;
            this.score = score;
        }
    }

    static int MAX_DAY = 1001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int n = Integer.parseInt(br.readLine());
        // 마감 일자가 늦은 순서대로 정렬
        PriorityQueue<Task> pq = new PriorityQueue<>((o1, o2) -> o2.dDay - o1.dDay);

        // 입력값 저장
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            pq.add(new Task(d, w));
        }

        int answer = 0;
        PriorityQueue<Task> greedy = new PriorityQueue<>((o1, o2) -> o2.score - o1.score);

        for (int today = MAX_DAY; today > 0; today--) {
            // 현재 날짜를 기준으로 수행 가능한 과제를 누적
            if(!pq.isEmpty()){
                while(!pq.isEmpty() && today <= pq.peek().dDay)
                    greedy.add(pq.poll());
            }

            // 수행할 과제가 없음
            if(greedy.isEmpty()) continue;

            // 점수가 가장 높은 과제를 수행
            Task task = greedy.poll();
            answer += task.score;
        }

        System.out.println(answer);
    }
}