백준 24060 | 알고리즘 수업 - 병합 정렬 1
백준 24060 알고리즘 수업 - 병합 정렬 1 풀이
Problem 💻
오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.
크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다.
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
merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
if (p < r) then {
q <- ⌊(p + r) / 2⌋; # q는 p, r의 중간 지점
merge_sort(A, p, q); # 전반부 정렬
merge_sort(A, q + 1, r); # 후반부 정렬
merge(A, p, q, r); # 병합
}
}
# A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
# A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
i <- p; j <- q + 1; t <- 1;
while (i ≤ q and j ≤ r) {
if (A[i] ≤ A[j])
then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
}
while (i ≤ q) # 왼쪽 배열 부분이 남은 경우
tmp[t++] <- A[i++];
while (j ≤ r) # 오른쪽 배열 부분이 남은 경우
tmp[t++] <- A[j++];
i <- p; t <- 1;
while (i ≤ r) # 결과를 A[p..r]에 저장
A[i++] <- tmp[t++];
}
입력
첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다.
다음 줄에 서로 다른 배열 A의 원소 A1, A2, …, AN이 주어진다. (1 ≤ Ai ≤ 109)
출력
배열 A에 K 번째 저장 되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다.
예제 입력 1 복사
1
2
3
5 7
4 5 1 3 2
예제 출력 1 복사
1
2
3
4 5 1 3 2 -> 4 5 1 3 2 -> 4 5 1 3 2 -> 1 5 1 3 2 -> 1 4 1 3 2 -> 1 4 5 3 2 -> 1 4 5 2 2 -> 1 4 5 2 3 -> 1 4 5 2 3 -> 1 2 5 2 3 -> 1 2 3 2 3 -> 1 2 3 4 3 -> 1 2 3 4 5. 총 12회 저장이 발생하고 일곱 번째 저장되는 수는 3이다.
예제 입력 2 복사
1
2
3
5 13
4 5 1 3 2
예제 출력 2 복사
1
2
-1
저장 횟수 12가 K 보다 작으므로 -1을 출력한다.
Approach 1 ❌
- 병합 정렬의 의사 코드를 따라서 Merge와 MergeSort를 구현하였다.
- 배열의 시작이 0부터 시작하는 것을 적용해야했다.
- r을 포함하지 않도록 시도하였다.
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
void Merge(vector<int>& numbers, int p, int mid, int r)
{
...
// r 값을 포함하지 않는 식으로 구현했다.
while (i <= mid && j < r)
{
...
}
...
}
void MergeSort(vector<int>& numbers, int p, int r)
{
...
int mid = (p + r) / 2;
MergeSort(numbers, p, mid); // mid를 포함하지 않아버림
MergeSort(numbers, mid + 1, r);
Merge(numbers, p, mid, r);
}
int main()
{
...
MergeSort(numbers, 0, N);
...
}
- 위처럼 r값을 포함하지 않는 방식으로 구현하니 MergeSort에서 mid를 처리하지 않는 문제가 발생했다.
Approach 2 ⭕
- r값을 포함해서 처리하도록 수정
- N-1 까지 r값으로 처리 및 조건식에서 r을 포함하도록 수정
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
void Merge(vector<int>& numbers, int p, int mid, int r)
{
...
// r 값을 포함하여 구현하도록 수정
while (i <= mid && j <= r)
{
...
}
...
}
void MergeSort(vector<int>& numbers, int p, int r)
{
...
int mid = (p + r) / 2;
MergeSort(numbers, p, mid);
MergeSort(numbers, mid + 1, r);
Merge(numbers, p, mid, r);
}
int main()
{
...
MergeSort(numbers, 0, N - 1); // 이렇게
...
}
해당 문제는 의사 코드가 주어져서 의사 코드를 읽으면서 풀면 어렵지 않게 해결 가능한 수준의 문제였다. 다만 의사 코드에만 의존하여 풀어낸 느낌이여서 병합 정렬에 한번 더 이해하는 과정과 의사 코드 없이 풀이를 할 수 있도록 공부하는 과정이 필요하겠다는 생각이 들었다.
Solution 💡
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
75
76
77
78
#include <iostream>
#include <vector>
using namespace std;
int cnt = 0;
int K = -1;
int res = -1;
void Merge(vector<int>& numbers, int p, int mid, int r)
{
vector<int> temp(r - p + 1);
int i = p;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= r)
{
if (numbers[i] <= numbers[j])
{
temp[k++] = numbers[i++];
}
else
{
temp[k++] = numbers[j++];
}
}
while (i <= mid)
{
temp[k++] = numbers[i++];
}
while (j <= r)
{
temp[k++] = numbers[j++];
}
i = p;
k = 0;
while (i <= r)
{
numbers[i++] = temp[k++];
cnt++;
if (cnt == K)
{
res = numbers[i - 1];
}
}
}
void MergeSort(vector<int>& numbers, int p, int r)
{
if (p >= r)
{
return;
}
int mid = (p + r) / 2;
MergeSort(numbers, p, mid);
MergeSort(numbers, mid + 1, r);
Merge(numbers, p, mid, r);
}
int main()
{
int N;
cin >> N >> K;
vector<int> numbers(N);
for (int i = 0; i < N; ++i)
{
cin >> numbers[i];
}
MergeSort(numbers, 0, N - 1);
cout << res;
}
Reference 📄
https://www.acmicpc.net/problem/24060