[인프런/Greedy/최대수입스케줄]

<<풀이>>

 

import java.util.*;

class Lecture implements Comparable<Lecture> {
    public int money;
    public int time;

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

    @Override
    public int compareTo(Lecture ob) {
        //내림차순
        return ob.time -this.time;
    }
}




class Main {

    static int n, max = Integer.MIN_VALUE;
    public int solution(ArrayList<Lecture> arr) {
        int answer = 0;
        // 가장 큰 값을 우선 순위로 하는 priorityQueue 이다. Collections.reverseOrder() 가 없다면 반대이다.
        PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
        Collections.sort(arr);

        int j = 0;
        for(int i=max; i>=1; i--) {
            System.out.println(j);
            for( ; j<n; j++) {
                if (arr.get(j).time < i) break;
                pQ.offer(arr.get(j).money);
            }
            if (!pQ.isEmpty()) answer += pQ.poll();
        }

        return answer;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in) ;
        n = in.nextInt();
        ArrayList<Lecture> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int m = in.nextInt();
            int d = in.nextInt();
            arr.add(new Lecture(m, d));
            if (d>max) max = d;
        }

        System.out.println(T.solution(arr));
    }
}

 

 

이 번 풀이는 greedy 알고리즘 풀이 방식 즉, 매 순간 최고의 것을 추출해내는 알고리즘으로 푸는 문제이다.

 

이 풀이의 핵심은 2가지라고 볼 수 있다.

 

1. PriorityQueue(우선 큐)

2. Comparable로 내림차순 정렬

 

PriorityQueue 는 poll() 할 때 기본적으로 내부에서 가장 작은 값을 return 해준다.

 

하지만, 

 

  // 가장 큰 값을 우선 순위로 하는 priorityQueue 이다. Collections.reverseOrder() 가 없다면 반대이다.
        PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());

 

이렇게 "Collections.reversOrder()" 를  하게 되면 반대로 가장 큰 값을 return 해주게 된다.

 

Comparable 은 객체를 내림차순 또는 오름차순 하기 위해서 이전부터 많이 이용해 왔다.

 

그럼 이 두 가지 핵심을 가지고 정리를 해보자.

 

 

<<논리적인 흐름>>

 

이 문제의 풀이의 핵심은 가장 기간이 긴 강의를 우선순위로 해서 정렬을 한다.

 

만약 반대로 하게 된다면, 기간이 짧은 걸로만 비교 했을 때 기간이 짧은 걸로 인해 그 다음 짧은 것의 수강을 놓칠 수 있게 된다.

 

우리는 최고의 이득을 보기 위해서 기간이 덜 짧은 것도 같이 확인 하면서 진행해야 한다.

 

반대로 진행하면 이를 해결할 수 있다.

 

ex)

 

3일 2일 1일 이렇게 3개가 있다고 하면

 

우선 3일랄 생각했을 때 이미 1, 2일 꺼는 끝났기 때문에 선택 폭이 3일에서만 선택하면 된다.

 

2일랄 생각했을 때, 1일 꺼는 끝났기 때문에 2일 과 3일 꺼 중에 선택하면 된다. 이때 3일 것이 2일 때보다 큰 것이 있다면, 3일 것을 선택한다. 만약 2일 중에서 선택해버리면 이로 인해 더 큰 3일 값을 놓칠 수 있다.

 

마지막으로 1일랄 생각했을 때, 1, 2, 3일 전부를 할 수 있다. 이미 반대로 오고 있었기 때문에 제일 큰 값들인 3일 2일 값들은 정해졌고 그 다음 제일 큰 값이 3일 또는 2일 또는 1일에서 선택할 수 있다.

 

이렇게 하면 결과적으로 최대의 이윤을 남기고 강의를 돌 수 있다.

 

---

 

 

알고리즘 공부는 언제나 많은 생각들을 하게 되고 이로인해 논리적인 사고의 흐름을 키울 수 있다.

 

당장 무조건 어려운 문제를 풀기보단

 

현재 풀어왔던 알고리즘을 한 번 더 짚어보면서

 

알고리즘에 익숙해지도록 해야겠다.

 

오늘도 수고했다 지호야 ~~