/<> 백준 16566번 : 카드 게임 (C언어)

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

 

 

철수가 낸 카드에 맞춰 민수는 효율적으로 카드를 내야 합니다. 우선 민수의 카드 배열을 오름차순으로 정렬해주고, 유니온 파인드(union-find)를 사용해주면 됩니다. 이때 부모 배열의 인덱스의 값을 카드의 숫자와 동일하게 초기화합니다. 즉 parent[i] = i 의 형태로 초기화합니다.

 

철수가 낸 카드보다 최소한으로 큰 카드를 내기 위해서 부모 배열을 업데이트할 때, 낸 카드의 부모를 오른쪽 숫자(인덱스)로 맞춰주면 됩니다. 이를 표로 통해 설명하자면, 다음과 같이 초기화를 완성한 상태입니다.

인덱스	1	2	3	4	5	6	7
부모	1	2	3	4	5	6	7

 

민수의 카드는 1부터 7까지 있고, 처음에 철수가 4를 냈다고 가정해봅시다. 그럼 민수의 카드 배열에서 4보다 첫번째로 큰 숫자를 찾습니다. 그럼 탐색을 통해 5인 것을 찾았습니다. 그럼 부모 배열에서 인덱스 5의 루트를 철수의 카드 배열에서 뽑으면 됩니다. 즉 탐색으로 값이 5인 것을 찾았습니다. 그럼 minsue[find[5]]를 내면 됩니다. 내고 난 뒤 parent[5]의 부모를 오른쪽 6으로 바꿉니다.

 

인덱스	1	2	3	4	5	6	7
부모	1	2	3	4	6	6	7

 

왜 오른쪽으로 바꾸냐면 그 다음에 철수가 다시 4를 냈다면, 탐색을 통해 다시 5를 찾을겁니다. 민수의 카드 배열에서 아까 뽑은 5를 지우지 않았기 때문이죠. 다시 minsue[find[5]]를 내면 부모 배열의 업데이트에 의해 5가 아닌 6을 내게 됩니다. 그래서 민수의 카드 배열에서 지우지 않아도 됩니다. 이 과정이 끝난 후 부모 배열의 인덱스 6의 값도 오른쪽 숫자 7로 바꿔줍니다.

 

인덱스	1	2	3	4	5	6	7
부모	1	2	3	4	6	7	7

 

철수가 또 다시 4를 내더라도 위와 같은 방식으로 민수는 minsue[find[5]] = 7을 내게 됩니다. 이렇게 유니온 파인드를 활용하여 문제를 해결할 수 있습니다.

 

 

<코드>

#include <stdio.h>
#include <stdlib.h>

int n, m, k;
int minsue[4000001];
int chulsue[10001];
int parent[4000001];
int temp[4000001];  // merge sort에 사용할 임시 배열

void merge(int arr[], int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = left;

    while(i <= mid && j <= right) {
        if(arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }

    while(i <= mid) temp[k++] = arr[i++];
    while(j <= right) temp[k++] = arr[j++];

    // 임시 배열을 원본 배열로 복사
    for(i = left; i <= right; i++) arr[i] = temp[i];
}

void merge_sort(int arr[], int left, int right) {
    if(left < right) {
        int mid = (left + right) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int find(int x) {
    if(parent[x] == x) return x;
    else return parent[x] = find(parent[x]);
}

void union_find(int a, int b) {
    int x = find(a);
    int y = find(b);
    parent[x] = y;
}

int main() {
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 1; i <= m; i++) scanf("%d", &minsue[i]);
    for(int i = 1; i <= k; i++) scanf("%d", &chulsue[i]);

    merge_sort(minsue, 1, m); // 민수의 카드 배열을 정렬
    
    for(int i = 1; i <= m; i++) parent[i] = i; // 부모 배열 초기화

    for(int i = 1; i <= k; i++) {
        int curr = chulsue[i];
        int left = 1, right = m;

        while(left <= right) {
            int mid = (left + right) / 2;
            if(minsue[mid] <= curr) left = mid + 1;
            else right = mid - 1;
        }

        int idx = find(left);
        printf("%d\n", minsue[idx]);

        union_find(idx, idx + 1); // 사용한 카드의 부모를 오른쪽 숫자로 업데이트
    }

    return 0;
}

 

 

시간 복잡도를 줄이기 위해 철수가 낸 값보다 첫번째로 큰 민수의 카드를 찾을 때 이분 탐색(binary search)를 사용합니다.

 

그리고 문제를 풀 때 C언어의 눈물을 찾았습니다... 처음 민수의 카드 배열을 정렬할 때 코드의 간결함(내가 편함)을 위해 qsort를 사용했는데, 계속 시간 초과가 떴습니다. C언어의 라이브러리 내장 함수 qsort()는 정렬 알고리즘 퀵소트(quick sort)에서 나온 함수입니다. 퀵소트의 최악의 시간 복잡도는 O(n^2)이기 때문에 모든 경우의 수를 검사하는 백준 채점 시스템에서 시간 초과가 나온 것입니다.

 

근데 C++이나 파이썬의 정렬 내장 함수는 최악의 시간 복잡도가 O(nlogn)이라서 이런 일이 생기지 않습니다... 그래서 코드를 보면 최악의 시간 복잡도가 O(nlogn)인 합병 정렬(merge sort)을 사용한 것입니다. 슬슬 C++로 갈아탈 준비를 해야겠군요.