BOJ 24061 : 알고리즘 수업 - 병합 정렬 2

풀이 요약

병합 정렬

풀이 상세

1. 병합정렬을 구현한다. 구현 방식은 다음과 같다.

2. 병합정렬은 크게 2가지 작업으로 나뉜다.

   • 배열을 절반씩 쪼개어 나누는 작업
   • 쪼개어진 배열을 정렬 순서에 맞게 swap 한 후 쪼개진 두 배열을 합치는 작업

3. 배열을 절반씩 쪼개는 작업은 이분탐색을 활용하여 구할 수 있다. 현재 맨 처음 값과 끝 값을 구하고, 이에 대한 중간값을 찾은 후 처음~중간 , 중간+1~끝 으로 배열을 쪼갠다.

4. 쪼개어진 배열을 정렬 순서에 맞게 swap 한 후 쪼개진 두 배열을 합치는 작업은 다음과 같다.

   • 3개의 변수가 준비되어야 한다. 첫번째 쪼개진 배열의 시작 인덱스 l 와, 두번째 쪼개진 배열의 시작 인덱스 r 그리고 쪼개진 두 배열이 합해질 때 각 수들을 어느 인덱스에 넣어야 하는지 필요한 idx 이다.
   • 조합할 임시 배열을 먼저 만든 후, 각각 쪼개어진 두 배열을 두 시작 인덱스를 기준으로 비교한다. 오름차순을 한다고 가정했을 때, v[l]<v[r] 이라면 임시배열에 첫번째 쪼개진 배열의 값을 넣고, 반대라면 두번째 쪼개진 배열을 넣는다.
   • 이후 기존의 원래 배열을 임시 배열을 기반으로 업데이트 해준다.

5. 현재 문제는 $K$ 번 변경 되었을 때의 배열을 구하는 문제이다. 병합정렬에서 변경되는 경우는, 임시배열을 토대로 업데이트 할 때 이므로, 업데이트 마다 카운트를 늘려 $K$ 에 도달했을 때의 현재 배열 값을 출력하면 된다.

배운점

• 저번에 전역변수에 배열을 30만개 이상 생성하는 경우, 에러가 났던 것으로 기억한다. 사람들이 알고리즘을 풀 때 배열을 사용해서 쓰라는 것이 이런 점 때문인가 보다. Java 의 List 보다 간편한 점이 많아 좋다. array 와 List 를 반반 섞은 느낌이랄까?

#include <iostream>
#include <vector>

using namespace std;
int N, K, cnt;
vector<int> v;

void printK() {
    for (int i = 0; i < N; i++) {
        cout << v[i] << " ";
    }
}

void merge(int st, int ed, int mid) {
    int buff[N];
    int l = st;
    int r = mid + 1;
    int idx = st;
    while (l <= mid && r <= ed) {
        if (v[l] < v[r]) {
            buff[idx++] = v[l++];
        } else {
            buff[idx++] = v[r++];
        }
    }

    while (l <= mid) {
        buff[idx++] = v[l++];
    }

    while (r <= ed) {
        buff[idx++] = v[r++];
    }

    for (int i = st; i <= ed; i++) {
        v[i] = buff[i];
        if (++cnt == K) printK();
    }
}

void merge_sort(int st, int ed) {
    if (st >= ed) return;
    int mid = (st + ed) / 2;
    merge_sort(st, mid);
    merge_sort(mid + 1, ed);
    merge(st, ed, mid);
}

void solve() {
    cin >> N >> K;
    int num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        v.push_back(num);
    }
    merge_sort(0, N - 1);
    if (cnt < K) cout << -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
}