[코딩테스트] PriorityQueue를 이용한 문제

📌 문제

• N개이 기업에서 강연 요청을 해왔는데, 각 기업은 D일 안에 와서 강
  연을 해 주면 M만큼의 강연료를 주기로 했다.
• 각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다.
• 단 강연의 특성상 현수는 하루에 하나의 기업에서만 강연을 할 수 있다.

📌 내가 풀이한 방법

1. D를 기준으로 들어온 값들을 정렬한다. (큰 값)
   → 기한이 큰것이 더 여유가 有
   ( ex : 10일 안에만 가면 되니까 기한이 큰것들은 계속 누적 )
2. max 값을 제일 상단의 값으로 잡고, 이후 값들을 계산

⬇️ 첫 번째 값 풀이 ( ⛔ 오답 )

static public int solution(Speech[] arr,int n) {
		PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
		Arrays.sort(arr);
		int max = arr[0].d;
		int sum=0;
		for(int i=0;i<n;i++) {
			if(max==arr[i].d) {
				pQ.offer(arr[i].p);
			}else {
				sum+=pQ.poll();
				pQ.offer(arr[i].p);
				max-=1;
			}
        }
		sum+=pQ.poll();
		return sum;
	}

오답 이유

• max값 : 3,2,1과 같은 순차값만 있을거라 생각하고 -1을 했지만, 비연속적인 값이 올 수도 있으므로 max값을 위와 같은 기준으로 잡고 문제 풀이하면 안됐음.

따라서 정답인 풀이는 다음과 같다
⬇️ 정답 풀이

static public int solution(Speech[] arr,int n) {
		PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
		Arrays.sort(arr);
		int max = arr[0].d;
		int sum=0;
		int j=0;
		for(int i=max;i>=1;i--) {
			for(;j<n;j++){
				if(arr[j].d<i) break;
				else pQ.offer(arr[j].p);
			}
			if(!pQ.isEmpty()) sum+= pQ.poll();
		}
		return sum;
	}

▪️ j를 밖에 둔 이유 : j값을 저장해서 그 순서부터 순환해야함

만약, for(int j=0;j<n;j++)과 같이 지정한다면 계속 큰 값이 들어감

📌 전체 정답 코드

import java.util.*;
public class Main {
	static public int solution(Speech[] arr,int n) {
		PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
		Arrays.sort(arr);
		int max = arr[0].d;
		int sum=0;

		int j=0;
		for(int i=max;i>=1;i--) {
			for(;j<n;j++){
				System.out.println(arr[j].p+": "+arr[j].d);
				if(arr[j].d<i) break;
				else pQ.offer(arr[j].p);
			}
			if(!pQ.isEmpty()) sum+= pQ.poll();
		}
		return sum;
	}
	static public void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		Speech[] arr = new Speech[n];
		for(int i=0;i<n;i++) {
			arr[i] = new Speech(sc.nextInt(),sc.nextInt());
		}
		System.out.println(solution(arr,n));
		
	}
	static class Speech implements Comparable<Speech>{
		public int p,d;//pay,day
		Speech(int p,int d){
			this.p=p;
			this.d=d;
		}
		@Override
		public int compareTo(Speech s) {
			return s.d-this.d;
		}
	}
	
}