섹션 9. Greedy Algorithm 4. 최대수입스케쥴( PriorityQueue)

문제

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

입력

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

출력

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

입출력 예제

---

풀이방식

이번 문제는 그리디 알고리즘에 대한 문제이다.

그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

---

설계과정

1. Lecture 객체를 통해 일자를 내림차순으로 정렬한다.

2. 일자가 큰 값부터 탐색한다.

3. 최대 일자부터 1일씩 줄며 해당 일자에 해당하는 강의 수입들을 Q에 넣는다.

4. 해당 일자에 해당하는 강의 수입 중에서 가장 큰 값을 큐에서 빼고 결과 변수에 누적한다.

5. 누적된 결과 변수를 출력한다.

---

풀이과정

1. 각 변수들을 선언한다.

• 강의 수입과 강의 일자를 갖고 있는 클래스 Lecture를 가진 ArrayList 배열  arr[ ] 을 선언한다.
• 강의 수입을 의미하는 변수 money 을 선언한다.
• 강의 일자를 의미하는 변수 date 을 선언한다.
• 최대값을 저장할 변수 max 을 Integer.MIN_VALUE 를 통해서 최소값으로 초기화한다.
• 결과값을 저장할 변수 result 을 선언한다.

2. 강의 수입과 강의 일자를 갖고 있는 Lecture 객체를 배열에 넣어서 내림차순으로 정렬한다.

 

3. 일자가 큰 값부터 1까지 줄면서 탐색한다.

• date 가 3이라면, 최대 3일까지 시간이 있다는 의미이다. 즉 1, 2, 3 일 모두 가능하기에 위처럼 탐색한다.

4. 입력된 값을 일자가 큰 강연료값부터 큐에 넣고, 해당 일자에 해당하는 금액들이 모두 들어가면 break한다.

• 해당 일자에 해당하는 강의만 확인하고, 그 중 큰 값을 비교하기 위해서이다.

5. 큐에 들어간 값들 중에서 가장 큰 값을 빼서 result 변수에 넣는다.

• 해당 일자에 해당하는 강연 중에서 가장 큰 강연료를 꺼내서 result 변수에 넣는 과정이다.

6. 위 과정을 반복하며 result 변수에 값을 누적한 후에 출력한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.