백준 11582번 - 치킨 TOP N(C++)

문제

https://www.acmicpc.net/problem/11582

11582번: 치킨 TOP N

풀이

간단하다. 머지 소트를 돌리다가 조건을 만족하면 중간에 정렬을 멈추는 것이다.
하지만 난 이 간단한 문제에 갈피를 못잡고 뻘짓을 하다가 강사님의 힌트를 보고 광명을 찾았다.
내가 한 뻘짓은 my_merge() 함수에서 지금 정렬중인 인원이 입력으로 주어진 인원보다 적으면 바로 리스트를 출력하도록 코드를 짰는데, 생각해보니 이게 왼쪽 서브리스트의 정렬이 이루어진 다음에 오른쪽 서브리스트의 정렬이 이루어져서 왼쪽 서브리스트에서 리스트 출력 조건을 만족해버리면 오른쪽 서브리스트는 정렬이 이루어지지 않은 상태로 바로 출력이 돼버린다.
이 문제의 해결 방법은 완전 간단한데... 그냥 if (e - s > n / limit) return;로 그냥 인원을 만족하는 순간 return; 해버려서 목표 인원을 넘어가는 순간 정렬을 멈추는 방법이다. 참고로, e - s는 지금 정렬중인 리스트의 크기고, n / limit는 전체 배열 크기에서 입력받은 인원 수를 나눈 것이다. 4명이 정렬중이라고 하면 인원 당 정렬중인 배열의 크기는 8 / 4인 2이기 때문에 이런 식으로 코드를 작성할 수 있다.

나의 코드

#include <iostream>

using namespace std;

int a[1048577];
int b[1048577];
int n, cnt, limit;

void my_merge(int s, int e) {
    if (e - s > n / limit) return;
    int mid = (s + e) / 2;
    int i = s, j = mid + 1, k = 0;
    while (i <= mid && j <= e) {
        if (a[i] <= a[j]) b[k++] = a[i++];
        else b[k++] = a[j++];
    }
    while (i <= mid) b[k++] = a[i++];
    while (j <= e) b[k++] = a[j++];
    for (int i = s; i <= e; i++) a[i] = b[i - s];
}

void merge_sort(int s, int e) {
    if (s == e) return;
    int mid = (s + e) / 2;
    merge_sort(s, mid);
    merge_sort(mid + 1, e);
    my_merge(s, e);
}

int main(int argc, const char * argv[]) {
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    cin >> limit;
    merge_sort(0, n-1);
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

위에서 실컷 떠들었기 때문에 코드에 대한 코멘트는 딱히 적지 않겠다.