최대 수입 스케줄(PriorityQueue 응용문제)

in Algorithm on Java, Coding, Test

문제

설명

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

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

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

입력

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

출력

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

예시 입력 1

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

예시 출력 1

150

해결방법

  • 일자의 의미를 잘 파악할 것. 1,2,3일 안에 와야한다는 것은 3일째 강의 부터 체크 해야 함을 의미
    • 3일안에 와야하는 강의 부터 3일자 스케줄부터 짠다는 것.
    • 현재 보다 멀리 있는 일자의 강의 부터 체크해서 큰 순서대로 스케줄을 짜겠다.
  • 우선 순위 큐를 활용하여 큐의 정렬 기준을 수입 기준으로 하여 생성한다.
  • 이후, 체크 하면서 큐에 넣으면 자동으로 수입 기준으로 정렬된다. → 바로바로 꺼내면 최대 값이 나온다.
  • 즉, 여기서 유심히 체크해야 되는 것은 1,2,3일 안에 스케줄 짜는 방법을 어떻게 하는가 이다.
    • 1일자에는 1,2,3일자 갈 수 있다.
    • 2일자에는 2,3일자 갈 수 있다.
    • 3일자에는 3일자 밖에 못간다.
    • ⇒ 즉, 3일자 스케줄부터 체크하면서 내려오면 된다.

코드

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;
    // 우선 순위 큐 생성하여 3일 -> 1일 순으로 정렬 기준 삼기 (데이터 넣는게 아님)
    PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
    Collections.sort(arr); // 재정렬 (일자순대로)
    int j = 0;
    // 아까 정의한 최대 일수 만 큼 반복하는데 역으로 반복함.
    for (int i = max; i >= 1; i--) {
      // 스케줄 개수 만큼 반복
      for (; j < n; j++) {
        // 일자 순서대로 뽑는데, 현재 체크하고 있는 스케줄 일자보다 작다? 체크하지 않음.
        if (arr.get(j).time < i) break;
        // 일자와 같다 -> 우선 순위 큐에 넣는다.
        pQ.offer(arr.get(j).money);
      }
      // 해당 일수에 최대 수입을 갖는 금액을 더한다.
      // 3일자 체크 후, 2일자로 넘어가면 3일자 30, 2일자 50, 2일자 40 이렇게 들어가 있음.
      // 따라서, 2일자에서 3일자를 갈 수도 있음. (3일자 금액이 2일자 보다 크다면)
      for(Integer z : pQ) System.out.println("money : " + z);
      if (!pQ.isEmpty()) answer += pQ.poll();
    }
    return answer;
  }

  public static void main(String[] args) {
    Main T = new Main();
    Scanner kb = new Scanner(System.in);
    n = kb.nextInt();
    ArrayList<Lecture> arr = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      int m = kb.nextInt();
      int d = kb.nextInt();
      arr.add(new Lecture(m, d));
      if (d > max) max = d; // 3일 -> 2일 -> 1일 순으로 체크하기 위해 반복 최대값 선언
    }
    System.out.println(T.solution(arr));
  }
}

© 2024. Chiptune93 All rights reserved.