[Algorithm] 최대 수입 스케쥴(PriorityQueue)

설명

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

 

풀이 과정.

강연료가 높을 수록 수입이 커지지만

강의마다 "D일 안에 해야한다" 라는 조건과 "하루에 1개만 가능하다"는 조건이 있다.

위의 예시처럼 M과 D를 입력을 받았다고 하고 구상을 해본다. * 이미 구한 값은 제외한다.

 

M D

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

 

D(큰값)가 D(작은값)보다 천천히(늦게) 강의를 해도 된다. (날짜 여유가 있으니까)

 

예를들어 보자.

 

D3는 D1, D2보다 늦게 해도되고

D2는 D1보다 늦게해도 된다.

이말은 즉 D1보다 늦게해도 되는 값은 D2, D3 두가지가 된다.

이렇게 D중 가장 큰 값부터 내림차순으로 비교를 하면서 진행하면 된다.

 

더 쉽게 풀어보자.

 

마지막 3일에 할 수 있는 가장 높은 강의를 구한다. 3일중에 구한다.

3일중에 강의료가 가장 큰 값을 구한다.

(30 3 / 60 3) -> 60 3

 

마지막 2일에 할 수 있는 가장 높은 강의를 구한다. 2~3일중에 구한다. 

2~3일중에 강의료가 가장 큰 값을 구한다.

(30 3 / 50 2 / 40 2) -> 50 2

 

마지막 1일에 할 수 있는 가장 높은 강의를 구한다. 1~3일중에 구한다.

1~3일중에 강의료가 가장 큰 값을 구한다.

(30 3 / 40 2 / 30 1 / 20 1) -> 40 2

 

이렇게 최대(D)부터 최소(D)까지 각각의 최적의 값을 구한 후 다 더하면 된다.

 

 

풀이.

class Company implements Comparable<Company>{
    public int pay;
    public int day;
    Company(int pay, int day) {
        this.pay = pay;
        this.day = day;
    }
    @Override
    public int compareTo(Company ob){
        return ob.day - this.day;
    }
}

class Main {
    static int n;
    static int max = Integer.MIN_VALUE; // D의 최댓값을 담을 변수
    static int result = 0;

    static void solution(ArrayList<Company> arr){
    	// PriorityQueue의 default는 오름차순으로
    	// Collections.reverseOrder()사용하여 내림차순으로 정렬하도록 한다.
        PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
        // Comparable인터페이스의 compareTo를 사용하여 
        // Company객체를 담고 있는 list를 인스턴스변수 D를 기준으로 내림차순 정렬한다.
        Collections.sort(arr);
        int j=0; // for문의 초기값 j를 외부 선언.
        for(int i=max; i>=1; i--){ // 최대D부터 역순으로 내려간다.
            // 초기값을 외부에 선언하여 중간에 나갔다 다시들어와도 이어서 진행하도록 한다.
            for( ; j<n; j++){ 
                if(arr.get(j).day<i) { // D값이 다르면 break로 나간다.
                    break;
                }else{ // D값이 같으면 PriorityQueue에 담는다.
                    pQ.offer(arr.get(j).pay);
                }
            }
            // 내림차순으로 정렬된 PriorityQueue에서 값(가장 큰 값)을 꺼내 결과를 누적한다.
            if(!pQ.isEmpty()) result += pQ.poll();
        }
    }
    
    public static void main(String[] args){
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        ArrayList<Company> arr = new ArrayList<>();
        for(int i=0; i<n; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            // 입력받은 값을 객체화 하여 arr에 담는다.
            arr.add(new Company(a, b));
            if(b > max) max = b;
        }
        solution(arr);
        System.out.println(result);
    }
}

 

---

 

정리 :

1. Comparable인터페이스의 compareTo메서드 사용하여 인스턴스 변수 day를 기준으로 내림차순으로 정렬한다.

2. PriorityQueue를 Collections.reverseOrder()로 생성하여 담긴 값을 poll()로 꺼낼 때 마다 최대값이 나오도록 한다.