최대 수입 스케쥴

최대 수입 스케쥴

현수는 유명한 강연자이다. N개이 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다.

각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다.

단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다.

입력 설명

첫 번째 줄에 자연수 N(1<=N<=10,000)이 주어지고, 다음 N개의 줄에 M(1<=M<=10,000)과 D(1<=D<=10,000)가 차례로 주어진다.

출력 설명

첫 번째 줄에 최대로 벌 수 있는 수입을 출력한다.

입력

6
50 2
20 1
40 2
60 3
30 3
30 1

출력

150

틀린 구현 코드

public class 최대수입스케쥴 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        ArrayList<Semina> list = new ArrayList<>();
        for(int i =0; i<n;i++){
            list.add(new Semina(in.nextInt(),in.nextInt()));
        }

        Comparator<Semina> comparator = new Comparator<Semina>() {
            @Override
            public int compare(Semina o1, Semina o2) {
                if(o1.day == o2.day){
                    return o2.pay - o1.pay;
                }
                return o2.day - o1.day;
            }
        };
        Collections.sort(list,comparator);

        int max_pay = 0;
        int max_day = list.get(0).day;
        PriorityQueue<Semina> priorityQueue = new PriorityQueue<>(new Comparator<Semina>() {
            @Override
            public int compare(Semina o1, Semina o2) {
                if(o2.pay == o1.pay){
                    return o1.day - o2.day;
                }
                return o2.pay - o1.pay;
            }
        });

        for(Semina s : list){
            if(s.day == max_day){
                priorityQueue.add(s);
            }
            else{
                //다른 경우
                Semina tmp = priorityQueue.poll();
                max_pay += tmp.pay;
                max_day = s.day;
                priorityQueue.add(s);
            }
        }

        if(!priorityQueue.isEmpty()){
            Semina tmp = priorityQueue.poll();
            max_pay += tmp.pay;
        }


        System.out.println(max_pay);
    }

    static class Semina{
        int pay;
        int day;
        public Semina(int pay,int day){
            this.pay = pay;
            this.day = day;
        }
    }
}

• 원래 생각했던 알고리즘
  list에 넣고 day기준 오름차순 정렬.
  priorityQueue는 pay 내림차순 정렬로 설정 후 for문 돌면서 max_day와 같은 경우에는 priorityQueue add. 아니면(새로운 day이면) priorityQueue에서 하나빼서 answer에 pay더하기.
  max_day 업데이트.

이런식으로 생각했음. 테스트케이스는 맞았지만 다음과 같은 경우에는 틀림.

입력:
10
13 2
18 1
68 10
72 8
11 7
41 2
48 7
15 7
34 1
13 8

출력:
302

입력을 정렬하면
68 10
72 8
13 8
48 7
15 7
11 7
41 2
13 2
34 1
18 1
만약 원래 짠 알고리즘으로 수행할 경우 테스트케이스와는 달리 이 입력은 날짜가 1씩 감소하는게 아닌 10 8 7 2 1로 감소하는 형태이므로 5개만 뽑고 멈춰버림. 문제는 가장 많이 벌 수 있도록 하는 것을 원하므로 맞지 않음.
따라서 날짜 내림차순으로 정렬한다음 max day를 기준으로 1씩 감소하면서 처리 필요.(3일날짜에 했던걸 2일날짜에는 당연히 할 수 있으니까)

모범답안 참고 후 구현 코드

 public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        ArrayList<Semina> list = new ArrayList<>();
        for(int i =0; i<n;i++){
            list.add(new Semina(in.nextInt(),in.nextInt()));
        }

        Comparator<Semina> comparator = new Comparator<Semina>() {
            @Override
            public int compare(Semina o1, Semina o2) {
                return o2.day - o1.day;
            }
        };
        Collections.sort(list,comparator);

        int max_pay = 0;
        int max_day = list.get(0).day;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

        int j=0;
        for(int i=max_day ;i>=1;i--){
            for(;j<n;j++){
                if(list.get(j).day<i) break;
                priorityQueue.offer(list.get(j).pay);
            }
            if(!priorityQueue.isEmpty()) max_pay+=priorityQueue.poll();
        }

        System.out.println(max_pay);
    }

    static class Semina{
        int pay;
        int day;
        public Semina(int pay,int day){
            this.pay = pay;
            this.day = day;
        }
    }

• 알고리즘

  ArrayList.add
  arrayList day기준 내림차순 정렬
  PriorityQueue 선언.(내림차순 기준)
  max day를 시작으로 하루씩 날짜 감소하면서 list 돌면서 max day보다 크거나 같은 경우에만 priorityQueue에 add.
  priorityQueue에서 하나 poll(현재 max_day 이상의 일중 pay가 가장 높은 것이 나올 것) 해서 answer add.