[JAVA] 알고리즘 문제풀이 - Greedy 기출문제 (최대 수입 스케쥴)
Greedy기출문제 풀이
최대 수입 스케쥴(PriorityQueue 응용문제)
- 설명 : 현수는 유명한 강연자이다. N개이 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다.
각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다.
단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다.
-
입력 : 첫 번째 줄에 자연수 N(1<=N<=10,000)이 주어지고, 다음 N개의 줄에 M(1<=M<=10,000)과 D(1<=D<=10,000)가 차례로 주어진다.
-
출력 : 첫 번째 줄에 최대로 벌 수 있는 수입을 출력한다.
-
풀이 답안
import java.util.*;
class Invite implements Comparable<Invite> {
int day;
int pay;
public Invite(int day, int pay) {
this.day = day;
this.pay = pay;
}
@Override
public int compareTo(Invite o) {
return o.day - this.day;
}
}
public class Main {
public void solution (List<Invite> list) {
int answer = 0;
int max = list.get(0).day;
int idx = 0;
PriorityQueue<Integer> pQ = new PriorityQueue(Collections.reverseOrder());
while(max>0){
for(int i=idx; i<list.size(); i++){
if(list.get(i).day!=max) {
idx = i;
break;
}
pQ.add(list.get(i).pay);
}
if(!pQ.isEmpty()) answer += pQ.poll();
max--;
}
System.out.println(answer);
}
public static void main(String[] args) {
Main main = new Main();
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
List<Invite> list = new ArrayList<>();
for(int i=0; i<num; i++){
int pay = scan.nextInt();
int day = scan.nextInt();
list.add(new Invite(day, pay));
}
Collections.sort(list);
main.solution(list);
}
}
- 정리
- 입력 데이터를 시간과 날짜로 담는 객체로 다시 만든다
- 리스트화 하여 날짜 순으로 정렬한다. (마지막날 선택할 강의를 먼저 뽑는 방식으로 진행)
- max변수에 최대일자를 담아주고, 역순으로 반복을 돈다
- 내부 반복을 통해 max와 같은 날짜의 데이터만 우선순위큐에 담아준다
- 이때 우선순위 큐는 최대값을 반환할수있도록 reverseOrder로 생성한다
- 다른 날짜가 나타나면 우선순위에 담는 과정을 진행하지 않고 바로 break, 대신 idx를 현재 i값으로 바꾸어줌 (이중으로 담아지지 않게하기 위함)
- 해당일자에 대한 금액을 모두 큐에 담았다면 poll하여 최대값을 출력하고 answer에 더해줌
- 다음날짜를 알기위해 max를 감소해줌
- 반복문이 끝나면 모든 일자를 순회한 것이므로 중단하고 answer 출력
- 입력 데이터를 시간과 날짜로 담는 객체로 다시 만든다