그리디 알고리즘 입문 문제 중 하나로 꼽히는 회의실 배정 문제다.
2개월?3개월 쯤 전 막 알고리즘 문제를 풀기 시작했던 시점에 이 문제가 너무 어려워서 보다가 때려 치웠던 기억이 난다.
근데 지금 다시 풀어보니까 너무 쉽다.
눈 감고도 풀 수 있을 듯 ㅎ (불가능)
나 같이 알고리즘 기초 문제도 어려워서 내가 이렇게 지능이 낮았나 자괴감 들고 자존감이 뚝뚝 떨어지는 사람이 있다면 기운내자.
계속 풀어보면 다 별 것 없다. 지금까지 살아오면서 겪은 일들이 늘 그랬듯이 말이다.
예전에 어렵게 느낀 문제를 너무 쉽게 풀었더니 감회가 새로워서 잡소리가 길었다.
우선 문제를 읽고 분석해보자.
내가 처음 작성한 주석은 다음과 같다.
(오늘은 평소와 달리 글을 작성하면서 푼 게 아니라 다 풀고 작성하는 것이지만 시행착오는 그대로 넣었다.)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
// 각 회의마다 시작시간, 끝나는 시간 주어짐
// 회의가 겹치지 않게 하면서 사용할 수 있는 회의 최대 개수
// 회의는 도중에 중단될 수 없음
// {1, 4} {5, 7} {6, 10} {2, 13}
// {3, 5} {3, 8} {8, 11} {12, 14}
// {0, 6} {5, 9} {8, 12}
// 최소값이 0 최대값이 14
// 1. n2가 작을 수록 좋다.
// 2. n2 - n1이 작을 수록 좋다.
// 3. n2와 다음 n1의 차이가 작을 수록 좋다.
// 그리티 알고리즘은 "해당 순간에 가장 최선인 경우를 모두 탐색하는 것"
// 1. 1-4 0-6 ? 1-4
// 2. 5-7 5-9 ? 5-7
// 3. 8-11, 8-12 ? 8-11
// 4. 12-14
// 시작 시간과 끝나는 시간은 2^31-1 == 정수형(Integer)의 범위를 의미한다.
|
cs |
이 문제는 어렵게 생각하면 끝도 없이 어려울 수 있지만, 그리디 알고리즘의 의의를 생각해보면 쉽게 풀이를 생각할 수 있다.
그리디 알고리즘은 탐욕 알고리즘이라는 이름에서 보이듯이 미래 같은 건 내 알 바 아니고, 무조건 최적의 해만 찾아가면 그만이다.
고난이도 문제에서는 다른 알고리즘들이 섞이면서 복잡해지지만, 적어도 이런 눈에 보이는 문제는 우리 상식 선에서 생각할 수 있는 최적의 해를 찾는 방법이 정답이라는 말이다.
1. 주어진 값 n1 n2를 정수형 배열 arr의 원소라고 생각했을 때, n2가 작다면 무조건 좋다.
=> 회의가 빨리 끝난다면 당연히 더 많은 팀원들이 회의실을 사용할 확률이 높아진다.
2. 이어지는 배열의 n1의 차이가 n2가 작을 수록 좋다.
=> 회의가 끝나자마자 해당 회의실을 다른 팀이 사용하는 것이 효율적이다.
이 두 가지 상식적인 원칙만 생각하면 나머지는 구현의 문제다.
마지막으로 시작 시간과 끝나는 시간은 2^31이라고 하는데, 이것은 정수형 범위를 의미한다.
이제 위 조건들을 활용해서 야매 수도코드를 작성해보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
public class Main {
public static void main(String[] args) throws Exception {
// 각 회의마다 시작시간, 끝나는 시간 주어짐
// 회의가 겹치지 않게 하면서 사용할 수 있는 회의 최대 개수
// 회의는 도중에 중단될 수 없음
// {1, 4} {5, 7} {6, 10} {2, 13}
// {3, 5} {3, 8} {8, 11} {12, 14}
// {0, 6} {5, 9} {8, 12}
// 최소값이 0 최대값이 14
// 1. n2가 작을 수록 좋다.
// 2. n2 - n1이 작을 수록 좋다.
// 3. n2와 다음 n1의 차이가 작을 수록 좋다.
// 그리티 알고리즘은 "해당 순간에 가장 최선인 경우를 모두 탐색하는 것"
// 1. 1-4 0-6 ? 1-4
// 2. 5-7 5-9 ? 5-7
// 3. 8-11, 8-12 ? 8-11
// 4. 12-14
// 시작 시간과 끝나는 시간은 2^31-1 == 정수형(Integer)의 범위를 의미한다.
// 회의의 수 N을 입력 받는다.
// 반복문 (i<N)
// 우선 순위 큐(정렬 기준 n2).push(배열)
// int answer = findBestValue(큐)
// 출력
}
public static int findBestValue(Queue<int[]> queue) {
// count = 0
// arr = null
// while (!queue.empty) {
// temp = queue.poll
// if ( arr에 등록된 배열의 n2보다 temp의 n1이 크다면 )
// arr = temp;
// count ++;
// }
// 반환
}
}
|
cs |
우선 우리는 회의가 빨리 끝나는 순서(n[1])대로 정렬하는 것이 중요한데, 나는 우선순위 큐를 사용했다.
Arrays.sort()가 아닌 우선순위 큐를 사용한 이유는 그냥 생각이 안 났기 때문이다. ㅎ
어느 방법을 사용하던지 별 차이는 없다.
둘 다 Comparator도 재정의해야 하고, 코드 길이도 비슷하니 익숙한 방법을 택하자.
단, PriorityQueue가 생각외로 여기저기 쓰이는 낭낭한 친구라서 익숙하지 않다면 배워놓는 게 좋다.
아무튼 정렬이 끝났다면 findBesetValue라는 함수로 들어간다.
무조건 끝나는 시간(arr[1])이 빠른 배열부터 반환되기 때문에 그 다음에는 시간 겹치지 않으면서 먼저 나오는 순서대로 죄다 체크하면 된다.
근데, 이대로만 풀면 틀린다.
위 주석에 고려하지 못한 부분이 2가지 있다.
1. 앞 팀이 나가자마자 다음 팀이 들어올 수 있다.
2. 어떤 팀은 들어가자마자 나갈 수 있다.(대체 왜?)
따라서 해당 부분을 수정만 하면.. 되는 게 아니라 아직 하나 더 있다.
Comparator가 익숙하지 않은 사람을 위해 이 부분은 바로 알려줄 예정인데 모두 스스로 풀고 싶으면 이제 나가삼
나도 Comparator는 여러번 쓰면서도 계속 헷갈린다.
|
1
2
3
4
5
6
|
Queue<int[]> queue = new PriorityQueue<>((n1, n2) -> {
if (n1[1] == n2[1]) {
return n1[0] - n2[0];
}
else return n1[1] - n2[1];
});
|
cs |
( 만약 회의 끝나는 시간이 같다면, 시작 시간이 빠른 배열을 앞으로 정렬하는 방법 )
( 재정의하지 않을 시 가장 마지막 수를 기준으로만 정렬함 )
람다를 모르면 자바의 정석 사서 자바를 다시 공부하자..
Arrays.sort()를 활용하든 PriorityQueue를 활용하든 Comparator를 재정의하는 방법은 별 차이가 없다.
아마 Arrays.sort(array, () -> { 어쩌고 저쩌고 })이러면 될 것 같은데 안해봐서 모름
아무튼 Comparator는 이해하려고 하면 헷갈린다. 그냥 외워라.
람다 파라미터 ( 첫번째놈, 두번째놈 )를 정하고
return 첫번째놈 - 두번째놈은 오름차순이다.
return 두번째놈 - 첫번째놈은 내림차순이다.
이유? 없다 그냥 약속이다.
있을지도 모르지만 우리 알 바 아니다. 일방적으로 정해진 약속이니까.
근데 조금만 더 깊게 들어가서 얘기하자면 사실 이게 좋은 방법은 아니다.
왜? 정수형 overflow나 underflow가 발생할 수 있기 때문이다. 뭔지 모르면 검색해보셈.
정석적으로 하자면 return if (n[1] == n2[1]) return Integer.compare(n1, n2)이렇게 해주면 좋다.
근데 지금까지 저렇게 했다고 오버플로우나 언더플로우 발생해서 틀려본 적은 없음. 그냥 TMI로 알려드림 ㅎ
이제 풀어보삼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
public class Main {
public static void main(String[] args) throws Exception {
// 각 회의마다 시작시간, 끝나는 시간 주어짐
// 회의가 겹치지 않게 하면서 사용할 수 있는 회의 최대 개수
// 회의는 도중에 중단될 수 없음
// {1, 4} {5, 7} {6, 10} {2, 13}
// {3, 5} {3, 8} {8, 11} {12, 14}
// {0, 6} {5, 9} {8, 12}
// 최소값이 0 최대값이 14
// 1. n2가 작을 수록 좋다.
// 2. n2 - n1이 작을 수록 좋다.
// 3. n2와 다음 n1의 차이가 작을 수록 좋다.
// 그리티 알고리즘은 "해당 순간에 가장 최선인 경우를 모두 탐색하는 것"
// 1. 1-4 0-6 ? 1-4
// 2. 5-7 5-9 ? 5-7
// 3. 8-11, 8-12 ? 8-11
// 4. 12-14
// 시작 시간과 끝나는 시간은 2^31-1 == 정수형(Integer)의 범위를 의미한다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 회의의 수 N을 입력 받는다.
int N = Integer.parseInt(br.readLine());
Queue<int[]> queue = new PriorityQueue<>((n1, n2) -> {
if (n1[1] == n2[1]) {
return n1[0] - n2[0];
}
else return n1[1] - n2[1];
});
// 반복문 (i<N)
for (int i=0; i<N; i++) {
// 우선 순위 큐(정렬 기준 n2).push(배열)
int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(e -> Integer.parseInt(e)).toArray();
queue.add(arr);
}
// int answer = findBestValue(큐)
int answer = findBestValue(queue);
// 출력
System.out.println(answer);
}
public static int findBestValue(Queue<int[]> queue) {
// count = 0
int count = 0;
// arr = null
int[] arr = null;
// while (!queue.empty) {
while (!queue.isEmpty()) {
// temp = queue.poll
int[] temp = queue.poll();
// if ( arr에 등록된 배열의 n2보다 temp의 n1이 크다면 )
if (arr == null || arr[1] <= temp[0]) {
// arr = temp;
arr = temp;
// count ++;
count++;
}
// }
}
// 반환
return count;
}
}
|
cs |
늘 그렇듯 주석은 무시하자.
'CS ﹒ Algorithm > Baekjoon' 카테고리의 다른 글
| Jav 문제풀이 (61) 거의 소수 (0) | 2022.11.06 |
|---|---|
| Java 백준 문제풀이 (60) 1541_잃어버린 괄호 (0) | 2022.11.03 |
| Java 백준 문제풀이 (58) 1744 _ 수 묶기 (0) | 2022.10.29 |
| Java 백준 문제풀이 (58) 1715 _ 카드 정렬하기 (0) | 2022.10.29 |
| Java 백준 문제풀이 (57) 1300 _ K번째 수 (0) | 2022.10.27 |
