백준 13904(JAVA)

문제

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

풀이

매일 하루에 하나씩밖에 과제를 하지못한다.
1 20
2 50
3 30
4 40
4 60
4 10
이런 입력이있으면 어떻게 해야 최대 점수를 받을수 있을까?
요소되는 날짜는 총 4일인데 해야할과제는 6개다. 즉, 2개를 버려야한다.
뭘 2개버려야할까? 바로 바로!!!! 점수가 제일 적은 과제 두개를 버려야한다
그럼 언제버려야할까?
언제버려야할지는 ArrayList와 우선순위 큐를 이용하면 알수있다.!!

• 과정
  먼저 너무 복잡하므로 입력되는 값을 소요되는 날짜가 적은 순으로 오름차순해서 정렬했다.
  그러면 저입력값은(변한게없긴하지만 다른 입력값들에 대해서는 정렬이된다.)
  1 20
  2 50
  3 30
  4 40
  4 60
  4 10
  요렇게 정렬이될것이다.!!

한 과제를 우선순위 큐에 넣을것이다. 우선순위큐의 정렬 기준은 버려야할 과제를 맨위에올리기위해서 점수의 오름차순으로 정렬하겠다.
이제 이 ArrayList에 저장된 값을 하나씩 우선순위 큐에 넣을것이다.
즉, 우선순위 큐의 size는 한 과제의 수를 즉, 과제를 하느라 소요된 날짜를(과제 하나당 하루가 소모됨), 입력되는 (소요되는 날짜가 오름차순으로 정렬된) 값의 날짜는 기한을 나타낸다.
이 둘을 비교하며 우선순위 큐에 넣으면되겠다
만약 과제를 세개해서 우선순위큐의 size가 3이면 (맨위에는 점수가 가장 적은 과제가 있을것이다.) 이때 day가 3인 과제가 입력되면 size + 1이 입력되는 day보다 크므로 해당 과제를 우선순위큐에 넣고 가장 점수가 작은걸 빼면된다.

간단하게 ArrayList에서 날짜가 가장 작은 순으로 우선순위큐에 넣는 과정을 살펴보자.

1. 1 20 -> pq size + 1이 입력되는 day 1보다 작거나 같으므로 pq에 offer [1 20]
2. 2 50 -> pq size + 1, 즉 2가 입력되는 day 2보다 작거나 같으므로 pq에 offer [1 20, 2 50]
3. 3 30 -> pq size + 1, 즉 3이 입력되는 day 3보다 작거나 같으므로 pq에 offer [1 20, 3 30, 2 50]
4. 4 40 -> pq size + 1, 즉 4가 입력되는 day 4보다 작거나 같으므로 pq에 offer [1 20, 3 30, 4 40, 2 50]
5. 4 60 -> pq size + 1, 즉 5가 입력된느 day 4보다 크므로!! pq에 이 값을 넣은다음 맨위에있는(점수가 제일작은)걸 뺴야한다. -> [1 20, 3 30, 4 40, 2 50, 4 60]에서 1 20이 빠지게된다.
   즉 5에서 pq는 [3 30, 4 40, 2 50, 4 60]이 된다. 즉, pq에서는 일수는 하나도 중요하지않다!!! (pq를 그냥 점수 Integer만 집어넣으면 더깔끔하겠다.)

과정을 하나씩 살펴보니 어렵지않다!! 이생각만하면 코드 구현은 훨씬쉽다.
아쉬운점은 우선순위큐에는 점수만 넣어도 무방하다는 것인데 그걸 생각못했다!! 리뷰하면서 생각이들었다.

코드

package baekjoon.그리디;

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

//5 -> 4 -> 2 -> 1 -> 7 (3, 6 포기)
//60 40 20 50 30 10 5

/**
 * 60 4
 * 40 3
 * 20
 * 50 2
 * 30 1
 * 10
 * 5  5
 */

class HomeWork implements Comparable<HomeWork>{
    int day;
    int score;

    public HomeWork(int day, int score){
        this.day = day;
        this.score = score;
    }

    public int getDay() {
        return day;
    }

    public int getScore() {
        return score;
    }

    @Override
    public String toString() {
        return "HomeWork{" +
                "day=" + day +
                ", score=" + score +
                '}';
    }

    @Override
    public int compareTo(HomeWork o) {
        return score - o.score; // 점수 오름차순
    }
}
public class Main13904 {
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        List<HomeWork> list = new ArrayList<>();

        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            list.add(new HomeWork(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        Collections.sort(list, Comparator.comparingInt(HomeWork::getDay));

        int result = calculateScore(list);
        System.out.println(result);
    }
    static int calculateScore(List<HomeWork> list){
        PriorityQueue<HomeWork> pq = new PriorityQueue<>();
        pq.offer(list.get(0));

        for(int i = 1; i < N; i++){
            int size = pq.size() + 1; // 만약 넣었을 때 pq size
            if(size <= list.get(i).getDay()){
                pq.offer(list.get(i));
            }else{
                pq.offer(list.get(i));
                pq.poll(); //제일 작은 점수의 숙제를 하지않음
            }
        }
        int sum = pq.stream().mapToInt(HomeWork::getScore).sum();
        return sum;
    }
}