최대수입스케쥴
2022. 3. 28. 12:25ㆍ코딩 테스트(JAVA)/인프런 문제풀이
설명
현수는 유명한 강연자이다. 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로 할당해줘야 합니다. 안 그러면 빈껍데기일 뿐입니다.
'코딩 테스트(JAVA) > 인프런 문제풀이' 카테고리의 다른 글
친구인가? (Disjoint-Set : Union&Find) (0) | 2022.03.29 |
---|---|
다익스트라 알고리즘 (수정 필요) (0) | 2022.03.28 |
결혼식 (0) | 2022.03.24 |
회의실 배정 (0) | 2022.03.24 |
씨름 선수 (0) | 2022.03.24 |