[BOJ] 백준 16466 콘서트

출처: https://www.acmicpc.net/problem/16466

Approach

합병 정렬(Merge Sort)  

합병 정렬(Merge Sort)

1차 티켓팅에서 팔린 티켓 목록을 알고 있으므로 그 티켓들을 제외하고 가장 낮은 번호의 티켓을 구하면 됩니다.

1차에서 최대 구매한 개수는 1,000,000개 이지만 티켓들의 총 개수는 231- 1 입니다

(만약 1차에서 1~1,000,000 번호까지 구매했다면 1000001이 요구하는 결과입니다.)

 

- 1차에서 구매한 N개의 티켓을 (병합)정렬로 오름차순 정렬시킵니다.

- 1~N까지 등장하지 않은 작은 수를 탐색합니다.

   arr = [1 2 4 7 8]일 때, 1(=arr[0])  → 2(=arr[1])  → 3(≠arr[2])

---

#include <stdio.h>
 
const int MAX_N = 1000000;
int arr[MAX_N], trr[MAX_N];
 
void mergeSort(int start, int end) {
    if (start >= end)
        return;
    
    int mid = (start + end) / 2;
 
    mergeSort(start, mid);
    mergeSort(mid + 1, end);
 
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j])
            trr[k++] = arr[i++];
        else
            trr[k++] = arr[j++];
    }
    while(i <= mid) trr[k++] = arr[i++];
    while(j <= end) trr[k++] = arr[j++];
 
    for (i = start; i <= end; ++i) {
        arr[i] = trr[i];
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
 
    int N, idx; scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", arr + i);
    }
 
    mergeSort(0, N - 1);
 
    int ans = 1;
    for (int i = 0; i < N; ++i) {
        if (ans != arr[i]) {
            break;
        }
        ans++;
    }
    printf("%d\n", ans);
}