[백준] 13904번 : 과제 – JAVA [자바]

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

---

문제

---

문제 풀이

문제 접근 방법:

1. 과제를 언제 수행할지 결정할지

• 하루에 하나의 과제만 수행할 수 있으므로, 우선순위를 정해야 함
• 마감일이 갈수록 나중에 수행할 여지가 있으므로, 이를 활용해야 함

2. 최대한 높은 점수를 받을 수 있도록 정렬하기 

• 마감일을 기준으로 정렬하되, 마감일이 같은 경우 점수가 높은 과제를 먼저 고려해야 함

3. 우선순위 큐를 활용하여 최적의 과제를 선택하기

• 우선순위 큐를 사용하여 현재 선택한 과제 중 점수가 가장 낮은 것을 추적함
• 이 이유는 새로운 과제를 추가할 때, 기존의 점수가 낮은 과제보다 더 높은 점수를 받을 수 있다면 교체해야 하기 때문이다

 

문제 해결 방법:

1. 과제 정렬: 

과제의 마감일을 기준으로 정렬하되, 마감일이 동일할 경우 점수가 높은 순서로 정렬한다.

 

2. 우선순위 큐 사용:

우선순위 큐를 사용해서 현재 할 수 있는 과제 중에서 점수가 가장 낮은 과제를 제거하고 새로운 과제, 점수가 더 높은 과제를 추가하는 방식으로 더 높은 점수를 얻는다.

 

3. 그리디 문제인 이유:

가능한 날까지 점수가 높은 과제를 선택하는 전략을 사용하기 때문에 이 문제는 그리디 문제다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Assignment[] arr = new Assignment[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            arr[i] = new Assignment(d, w);
        }
		
        // 마감일 기준 정렬, 동일한 마감일이면 점수가 높은 순서로 정렬
        Arrays.sort(arr, new Comparator<Assignment>() {
            @Override
            public int compare(Assignment o1, Assignment o2) {
                if (o1.d == o2.d) return Integer.compare(o2.w, o1.w);
                return Integer.compare(o1.d, o2.d);
            }
        });

        PriorityQueue<Assignment> pq = new PriorityQueue<>();
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (pq.size() < arr[i].d) {
                pq.add(arr[i]);
            } else {
                if (arr[i].w > pq.peek().w) {
                    pq.poll();
                    pq.add(arr[i]);
                }
            }
        }
        while (!pq.isEmpty()) {
            sum += pq.poll().w;
        }
        System.out.println(sum);

    }


    public static class Assignment implements Comparable<Assignment> {
        int d;
        int w;

        public Assignment(int d, int w) {
            this.d = d;
            this.w = w;
        }

        @Override
        public int compareTo(Assignment o) {
            return this.w - o.w;
        }
    }

}

 

 

---

코드 설명

1. 입력 받기:
BufferedReader를 사용해서 입력을 받고 Assignment 객체 배열에 저장한다. 이 Assignment 객체(클래스)는 마감일까지 남은 일수 d와 과제 점수 w를 저장한다.

 

2. 정렬

• 마감일(d)을 기준으로 오름차순 정렬한다.
• 만약 마감일이 같다면, 점수(w)가 높은 순서대로 정렬한다. 정렬은

3. 우선순위 큐

우선순위 큐 pq를 사용해서 현재 선택한 과제들 중 점수가 가장 낮은 과제를 추적하고 현재 수행할 수 있는 과제 개수가 마감일까지 남은 일수를 초과하면, 점수가 가장 낮은 과제를 제거하고 새로운 과제를 추가한다 (새로운 과제의 점수가 더 높을 때만).

 

4. 새 클래스인 Assignment를 만든 이유:

• PriorityQueue를 사용할 때, 기본적으로 정렬 기준이 필요하다. 
• 따라서, Comparable<Assignment>를 구현하면 compareTo 메서드를 정의해서 Assignment 객체 간의 정렬 기준을 만들 수 있다. 
• 여기서는 점수(w)를 기준으로 오름차순 정렬을 수행하도록 설정하여 우선순위 큐에서 가장 낮은 점수를 쉽게 찾을 수 있도록 해준다.

 

시간 복잡도 (Time Complexity)

 

정렬: O (N log N)

우선순위 큐 삽입 및 삭제: O (N log N)

총 시간 복잡도: O (N log N)