[JAVA]13904 과제, greedy , 골드3

 📚 문제  

13904번: 과제

🔍 아이디어  

그리디 알고리즘으로 해결하였습니다.

해당 문제는 과제의 마감일과 과제의 점수를 주고 최대 얻을 수 있는 과제 점수를 찾는 문제입니다.

 

저의 경우는 보통의 그리디와 같은 문제인줄 알고 먼저 배열을 마감일을 기준으로 오름 차순 정렬하였습니다.

그 이후에 마감일을 돌면서 해당 마감일 안에 해결할 수 있는 과제들이 있는 경우 우선순위 큐에 넣고 

큐에 값이 있는 경우 해당 날자에 해결 할 수 있는 문제가 있는 것임으로 점수가 가장 큰 것을 리턴하도록 하였습니다.

하지만 예제 출력 값과 달라 문제를 다시 읽어보니 마감일 내에 해결할 수 있는 과제들임을 한번 더 인지 하였습니다. 

 

즉 마감일이 6일차 까지 가능하다면 해당 과제는 1~6일 차 이내에만 해결하면 되는 과제입니다.

따라서 위에서 풀이하였던 방법의 역순으로 배열을 마감일을 기준으로 내림차순으로 정렬하였습니다.

이후에는 포문을 가장 넉넉했던 마감일부터 1일까지 돌며 해당 마감일 내에 해결할 수 있는 과제들을 큐에 넣었습니다.

그리고 큐에서 점수를 가장 많이 주는 과제를 우선으로 처리하며 각 날짜별로 가장 큰 점수를 얻을 수 있는 방법을 더하여 결과를 냈습니다.

 

예시) 

submit day	1	2	3	4	4	4	6
score	20	50	30	10	40	60	5

입력	queue의 상태
7 4 60 4 40 1 20 2 50 3 30 4 10 6 5

 

📝 풀이 

package 백준.greedy;

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

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

        int line = Integer.parseInt(br.readLine());
        int maxDay = 0;
        int[][] arr = new int[line][2];

        for (int i = 0; i < line; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            maxDay = Math.max(maxDay, arr[i][0]);
        }

        Arrays.sort(arr, ((o1, o2) -> o2[0] - o1[0])); //날짜가 많은 순으로(마감기한이 넉넉한 순서대로)
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]); //점수가 높은 순으로

        int idx = 0;
        int score = 0;
        for (int day = maxDay; 0 < day; day--) {
            while (idx < line && arr[idx][0] == day) {
                pq.add(arr[idx++]);
            }

            if (!pq.isEmpty()) {
//                System.out.println("선택" + Arrays.toString(pq.peek()));
                score += pq.poll()[1];
            }
        }

        System.out.println(score);
    }
}