최대수입스케쥴

설명

현수는 유명한 강연자이다. 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

 

문제 이해

 

내가 작성한 오류 코드

package ch09;

import java.util.*;

class Lecture implements Comparable<Lecture> {
	public int money, day;
	
	// 매개변수 있는 생성자
	Lecture(int money, int day) {
		this.money = money;
		this.day = day;
	}
	// 오버라이드, 정렬 기준
	@Override
	public int compareTo(Lecture l) {
		// day 내림차순 l - this : day를 내림차순으로 정렬 후 해당 money를 pQ에 넣기 위함
		return l.day - this.day;
	}
}

public class PriorityQueueTest {
	// static 변수 : class 내 사용가능, day를 원하는 만큼 넣기위한 tmp설정한 것
	static int max = Integer.MIN_VALUE; 
	
	public int solution(ArrayList<Lecture> arr, int n) {
		int answer = 0;
		// 정렬
		Collections.sort(arr);
		// 우선순위 큐 생성, 우선순위 기준 reverse(기본값은 최솟값)
		PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
		for(int i=max; i>=1; i--) {
			// pQ에 넣기
			for(int j=0; j<n; j++) {
				if(arr.get(j).day < i ) break;
				pQ.offer(arr.get(j).money);
			}
			if(!pQ.isEmpty()) answer += pQ.poll();
		}
		return answer;
	}

	public static void main(String[] args) {
		PriorityQueueTest T = new PriorityQueueTest();
		Scanner kb = new Scanner(System.in);
		// 입력 2개 : 총n, ArrayList로 Lecture (money, day) 받기
		int n = kb.nextInt();
		// ArrayList<데이터 타입> 생성
		ArrayList<Lecture> arr = new ArrayList<>();
		for(int i=0; i<n; i++) {
			int money = kb.nextInt();
			int day = kb.nextInt();
			arr.add(new Lecture(money, day)); // 객체 생성해서 넣음!
			// 위치 고민!
			if(day > max) max = day;
		}
		System.out.println(T.solution(arr,n));
	}

}

 

채점 결과

 

1) 입력값

10
13 2
18 1
68 10
72 8
11 7
41 2

 

2) 리턴값

712

 

3) 정답값

302

 

어디가 틀렸을까......

 

💡 int j =0; 의 위치에 따라서 정답/실패 코드로 나뉘는 것을 발견하였다.

 

정답 코드

package ch09;

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;
    }
}

public class PriorityQueueTest {
	static int max = Integer.MIN_VALUE; 

	public int solution(ArrayList<Lecture> arr, int n){
		int answer=0;
		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);
			}
			if(!pQ.isEmpty()) answer+=pQ.poll();
		}
		return answer;
	}


	public static void main(String[] args) {
		PriorityQueueTest T = new PriorityQueueTest();
		Scanner kb = new Scanner(System.in);
		int 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;
		}
		System.out.println(T.solution(arr,n));
	}

}

 

 for문안에 int j =0; 선언 시 부모 for문 돌 때마다 0으로 초기화되지만
 for문 밖으로 선언해버리면 0으로 초기화가 안됩니다!

 

 

💡 arr.add(new Lecture(m, d));처럼 객체를 생성해서 넣어야 하는 이유

array 배열에 타입이 Lecture 타입이니까 추가를 해주려면 new로 할당을 해줘야 합니다

클래스를 사용하려면 new로 할당해줘야 합니다. 안 그러면 빈껍데기일 뿐입니다.