[C++] 백준 24060. 알고리즘 수업 - 병합 정렬 1

문제

입출력

병합 정렬

합병 정렬이라고도 불리는 병합 정렬(Merge Sort)는
퀵소트와 함께 시간복잡도 O(nlogn)을 갖는 제법 빠른 정렬 기법 중 하나이다.

분명 싸피에서 이걸 배운 기억이 있는데
이번 문제를 보고 다시 공부하면서 댁알이가 깨져불 뻔 했다;
사실 손으로 계산해보기 귀찮아서 짱구를 열심히 굴려보다가
포기하고 손으로 써가면서 따라갔더니 이해가 잘 됐다.
머리가 나쁘면 몸이 고생해야지 응

병합 정렬은 정렬되지 않은 배열을 혼자가 될 때까지 쪼갠 뒤
가장 작은 단위 배열부터 마지막 반갈 배열까지 비교해가며 정렬하는 방법이다.

위키피디아의 예시로 들어가있는 GIF를 보고 느낌을 대강 잡고,
고 담에 코딩하는거니 요 분 영상 보고 내 걸로 만들 수 있었던 것 같음

풀이

그냥 병합 정렬 코드와 다른 점은 K번째 저장되는 수를 출력해줘야 한다는 것.
처음에는 L R 배열 나눠놓고 비교해서 냅다 원본 배열에 때려넣는 코드로 짰는데
카운트 수를 일일이 더해주는 게 별론 것 같았다.

그래서 비교하는 중에는 값들을 임시 배열에 넣어뒀다가,
원본 배열을 업데이트하며 카운트를 올리는 방식으로 변경했다.

재귀 함수다보니 출력값이 나왔는데도 끝나지 않는 게 맘에 안들어서
return을 여기 저기 끼워넣어서 조금이라도 빨리 끝나도록 해줬다.

코드

#include <iostream>
#include <vector>
using namespace std;

int N, K, cnt = 0;
bool flag = false;

bool merge(vector<int>& arr, int l, int m, int r) {
    vector<int> tmp(r - l + 1);
    int i = l;
    int j = m + 1;
    int k = 0;

    while (i <= m && j <= r) {
        if (arr[i] <= arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }

    while (i <= m)
        tmp[k++] = arr[i++];
    while (j <= r) {
        tmp[k++] = arr[j++];
    }

    k = 0;
    while (k < tmp.size()) {
        arr[l + k] = tmp[k];
        k++;
        cnt++;
        if (cnt == K) {
            cout << arr[l + k - 1];
            return true;
        }
    }
    return false;
}

bool mergeSort(vector<int>& arr, int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        if (mergeSort(arr, l, m)) return true;
        if (mergeSort(arr, m + 1, r)) return true;
        return merge(arr, l, m, r);
    }
    return false;
}

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

    cin >> N >> K;
    vector<int> arr(N);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    if (!mergeSort(arr, 0, N - 1)) cout << -1;

    return 0;
}

채점

나에겐 골드3보다 어려웠던.. 갈 길이 멀구나