[인프런 알고리즘 문제풀이] 최대 수입 스케쥴

문제

인프런 알고리즘 문제풀이

• The copyright in this matter is in Inflearn

입력1

6
50 2 
20 1 
40 2 
60 3 
30 3

출력1

150

풀이

d일을 기준으로 내림차순으로 a라는 배열에 비용과 날짜를 저장하면 아래와 같이 a배열에 값이 존재한다.

(60 3)
(30 3)
(50 2)
(40 2)
(30 1)
(20 1)

그리고 3일에서 시작하여 3일째에 강연이 가능한 비용을 최대힙모양인 우선순위큐에 넣고,
그 중 가장 큰 강연료를 뽑아내어 sum변수에 더해준다.
(pq = 60 30) -> 가장 큰 강연료 60을 큐에서 빼고 pq = (30), sum 변수에 60 더함

다시 2일째에 강연이 가능한 비용을 우선순위큐에 넣고, (pq = 50 40 30)
그 중 가장 큰 강연료 50 빼고 (pq = 40 30) sum변수에 50
이 과정을 1일까지 반복한다.

코드

/* 75. 최대 수입 스케쥴(priority queue) 이용 */
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.StringTokenizer;
import java.util.ArrayList;

class Main
{
    
    public static void main (String[] args) throws java.lang.Exception
    {
        
        System.setIn(new FileInputStream("input.txt"));
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        Schedule[] a = new Schedule[n];
        int max = -217000000;

        for(int i = 0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            if(max < y){
                max = y;
            }
            a[i] = new Schedule(x,y);
        }

        Arrays.sort(a);
        
        //우선순위큐 최대힙
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        int sum = 0;
        int j = 0;
        for(int i = max;i >0;i--){
            for( ;j<n;j++){
                if(a[j].day < i){
                    break;
                }
                pq.add(a[j].cost);
            }
            if(pq.size() != 0){
                sum += pq.poll();//값을 얻고, 삭제해줌
            }

        }
        System.out.println(sum);



    }
}

class Schedule implements Comparable<Schedule>
{
    int cost;
    int day;

    public Schedule(int cost, int day){
        this.cost = cost;
        this.day = day;
    }

    @Override
    public int compareTo(Schedule s){
        //return this.day <= s.day ? 1 : -1;//내림차순을 의미
        //return this.day > s.day ? -1 : 1;//내림차순을 의미
        return s.day - this.day;//내림차순을 의미
    }
}