목표
greedy 알고리즘 감각이 많이 부족하다.
최대 수입 스케줄을 풀면서 부족했던 점을 되짚어 보고 개선해보자.
문제 풀이
문제에서 하루에 하나의 일만 선택할 수 있다는 조건이 있다.
이 조건의 예시를 들어보면
50 2
40 2
30 1
20 1
위와 같이 스케줄이 주어졌을 때 date = 1에서의 최댓값인 money = 30을 고르는 것보다
date = 2에서의 50과 40을 고르는 것이 더 좋은 선택지가 될 수 있다.
이게 가능한 이유는 date = 2의 의미는 2일이라는 의미이기 때문이다.
2일 동안 2번의 일을할 수 있으므로 첫째날에 50만원의 일을 하고, 둘째날에 40만원의 일을하는게 더 많은 돈을 벌 수 있다.
그렇다면, 이 조건의 핵심이 date 값 만큼 일을 할 수 있다고 생각할 수도 있다.
date = 2일 때 두번의 일을 할 수 있고,
date = 3일 때 세번의 일을 할 수 있는 것 아닌가?
하지만, 그렇지않다.
예를 들어 아래와 같은 스케줄이 있다고 가정해보자.
68 5
30 2
20 1
40 2
위에서 나올 수 있는 스케줄 수는 3번이다. date = 5인데, 세번의 스케줄 밖에 수행하지 못한다.
date가 연속적일 때는 단순히 date 값 만큼 스케줄을 수행할 수 있었지만, date가 불연속적일 때는 date 값과 스케줄 수행 가능 값이 달라진다.
왜 정렬 방식을 date 오름차순으로 두었을까?
오름차순으로 두었을 때를 생각해보면 이해할 수 있다.
아래는 내가 주석을 통해 어떻게 논리적인 흐름을 가져갔는지 설명해준다.
문제에서 모든 스케줄을 이미 제공하고 그 스케줄내에서 최선을 선택해야 한다.
내림차순으로 주어졌을 경우에는 date가 높을 수록 선택의 여지가 많아진다고 볼 수 있다.
스케줄의 총 수가 9인데, date가 10이라면 해당하는 스케줄은 반드시 수행할 수 있다고 볼 수 있다.
예를 들어
8 10 // size = 9
12 8 // size = 8
10 7 // size = 7
8 7 // size = 6
6 7
40 2
30 2
15 1
10 1
위와 같이 스케줄이 주어졌을 때 date = 10, 8, 7 스케줄은 모두 수행할 수 있다.
즉, date가 size보다 같거나 크다면 반드시 수행할 수 있는 스케줄이라고 생각할 수 있다.
그러니 date를 내림차순으로 설계하는게 최선의 방법일 것이다.
solution logic
자세하게 이해하려면 디버깅을 해보는게 가장 좋다.
i = 9일 때 j = 1이다. arr.get(j).date = 8이므로 i 값이 더 크다. 그래서 break 되고, pQ.poll() 한 값을 answer에 넣어주는데 pQ size가 null인 상태이므로 if(!pQ.isEmpty()) 조건문을 달아줘야 한다.
전체 풀이 코드
package infrenalgorithm.greedy;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
class LectureTwo implements Comparable<LectureTwo> {
public int money;
public int date;
public LectureTwo(int money, int date) {
this.money = money;
this.date = date;
}
@Override
public int compareTo(LectureTwo o) {
return o.date - this.date;
}
}
public class 최대수입스케줄강사풀이 {
public int solution(ArrayList<LectureTwo> arr, int max, int n) {
int answer = 0;
PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
int j = 0;
for (int i = max; i >= 1; i--) {
for (; j < n; j++) {
if (arr.get(j).date < i) break;
pQ.offer(arr.get(j).money);
}
if (!pQ.isEmpty()) answer += pQ.poll();
}
return answer;
}
public static void main(String[] args) {
최대수입스케줄강사풀이 T = new 최대수입스케줄강사풀이();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
ArrayList<LectureTwo> arr = new ArrayList<>();
int max = Integer.MIN_VALUE;
for(int i = 0; i < n; i++){
int a = in.nextInt();
int b = in.nextInt();
if(max < b) max = b;
arr.add(new LectureTwo(a, b));
}
Collections.sort(arr);
System.out.println(T.solution(arr, max, n));
}
}
배운 점
PriorityQueue
PriorityQueue 자료구조에 대해 배웠다.
PriorityQueue와 Queue의 차이점을 이해했고 PriorityQueue를 어느정도 응용할 수 있게 되었다.
for문 응용
int j = 0;
for (int i = max; i >= 1; i--) {
for (; j < n; j++) {
if (arr.get(j).date < i) break;
pQ.offer(arr.get(j).money);
}
if (!pQ.isEmpty()) answer += pQ.poll();
}solution 로직에서 j를 저렇게 위에 선언해둘 수 있다는 사실을 처음 알았다.
어떻게 동작하는지 이해는 되었다.
arr.get(j).date < i일 때 break 하게 되면 다음 라인을 수행하지 않고 for문을 빠져나온다.
그리고 if (!pQ.isEmpty()) answer += pQ.poll(); 로직을 수행한 뒤에
i 값이 줄어든다.
만약 j 값을 for문 안에 아래와 같이 초기화 했다면
for (int j = 0; j < n; j++) {
if (arr.get(j).date < i) break;
pQ.offer(arr.get(j).money);
}j 값이 계속해서 0으로 초기화되어서 arr.get(j).date 값이 date 최댓값으로 유지되었을 것이고
원하는 값이 출력되지 않았을 것이다.
아쉬운 점
이 문제를 명확하게 이해하는데 너무 오랜 시간이 소요된 것 같다.
복잡한 문제를 해결해나가면서 내 지능에 대한 의심을 하게 된다..
내가 혹시 다른 사람들보다 지능이 떨어져서 복잡한 문제 해결 능력이 부족한가..?
나는 이 이길이 아닌가..?라는 의심이 들 때가 많다.
개선 방안 : 스스로 의심은 거두고 계속해서 더 좋은 방법을 찾아 개선해나가자!
greedy 알고리즘은 내게 너무 어렵다.
항상 최적의 해를 찾아나가면서 문제를 해결했는데
greedy 문제는 접근 방식이 현재 상태에서 최선의 선택을 하는거다 보니 최적의 해가 나오지 않게 될 수 있다.
이러한 점에서 문제 풀이에 어려움을 느끼는 것 같다.
개선 방안 : 아직은 감을 명확히 잡지 못했다. 비슷한 유형의 문제를 더 많이 풀어보고 감을 익히자
