★최대수입스케쥴(PriorityQueue)

 

3일 안에 와서 강연을 해도 되는거면 2일 전이든 1일 전이든 가서 하면 된다.

먼저 time을 기준으로 내림차순 정렬한다.

강연료가 큰 값을 기준으로 큐에서 빼야하니 우선순위 큐를 내림차순으로 사용한다.

3일 안에 오면 가능한 강연들을 큐에 넣고 최대 강연료가 되는 기업의 강연료를 구한다.

구한 강연료를 총 수입 answer 변수에 더하고 큐에서 뺀다.

2, 1일 안에 오면 가능한 강연들을 큐에 넣고 위의 과정을 반복한다.

(여기서 3일 안에 기업의 강연료가 높으면 선택이 될 수도 있다.)

 

이중 for문에서 안 쪽 for문에 대해 바깥에서 초깃값을 정의하면 그 값이 유지가 된다.

j = 2일 때 break; 됐다면 다음 for문이 돌 때 0, 1 이 아닌 2부터 시작한다.

 

안 쪽에서 초깃값을 정의하고

if(arr.get(j).time == i) pQ.offer(arr.get(j).money); 로만 돌려도 되지만

의미 없이도는 경우가 많아지니 위의 방법도 숙지해놓으면 좋을 듯하다.

 

 

import java.util.*;

public class Main {
    static int n, m, k, dis, max;
    static int[][] board;
    static int[] ch,combi,pm;
    static String[] split;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    //알파벳 방문여부
    static boolean[] checked = new boolean[26];
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        ArrayList<Lecture> list = new ArrayList<Lecture>();
        for(int i = 0; i < n; i++) {
            int m = kb.nextInt();
            int d = kb.nextInt();
            list.add(new Lecture(m, d));
            if(d > max) max = d;
        }
        Collections.sort(list);
        System.out.println(list);
        System.out.println(T.solution(list));
    }

    private int solution(ArrayList<Lecture> list) {
        int answer = 0;

        //3일 안에와서 하면 되는 강연은 1,2,3일 다 할 수 있음
        //우선순위를 둘건데 돈 많이 주는거 먼저 꺼내기
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

        int j = 0;
        //3,2,1일 순으로 강연넣고 최대 수입을 쌓기
        for(int i = max; i > 0; i--) {
            //이렇게하면 break;될 때 j값을 그대로 갖고 있는다.
            //j=2에서 멈추고 2에서부터 2일치를 다시 넣음
            for(; j < n; j++) {
                if(list.get(j).time < i) break;
                pq.offer(list.get(j).money);
            }
            System.out.println(pq);
            //해당 일자에서 뽑은 최대 수입을 더하기
            if(!pq.isEmpty()) answer += pq.poll();
        }


        return answer;
    }

    private static class Lecture implements Comparable<Lecture> {
        private int money;
        private int time;

        public Lecture(int money, int time) {
            this.money = money;
            this.time = time;
        }

        @Override
        public int compareTo(Lecture o) {
            return o.time-this.time;
        }

        @Override
        public String toString() {
            return "Lecture{" +
                    "money=" + money +
                    ", time=" + time +
                    '}';
        }
    }
}