[BOJ] 16566번 - 카드 게임

백준 16566번 - 카드 게임

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1.2 초	512 MB	1842	596	345	28.919%

문제

철수와 민수는 카드 게임을 즐겨한다. 이 카드 게임의 규칙은 다음과 같다.

1. N개의 빨간색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 M개의 카드를 고른다.
2. N개의 파란색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 빨간색에서 고른 번호와 같은 파란색 카드 M개를 고른다.
3. 철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다.
4. 철수와 민수는 고른 카드 중에 1장을 뒤집어진 상태로 낸다. 그리고 카드를 다시 뒤집어서 번호가 큰 사람이 이긴다. 이 동작을 K번 해서 더 많이 이긴 사람이 최종적으로 승리한다. 한 번 낸 카드는 반드시 버려야 한다.

철수는 뛰어난 마술사이기 때문에 본인이 낼 카드를 마음대로 조작할 수 있다. 즉, 카드를 버리고 민수 몰래 다시 들고 온다거나 민수한테 없는 카드를 내기도 한다.

민수는 뛰어난 심리학자이기 때문에 철수가 낼 카드를 알아낼 수 있다. 그래서 민수는 철수가 낼 카드보다 큰 카드가 있다면 그 카드들 중 가장 작은 카드를 내기로 했다.

K번 동안 철수가 낼 카드가 입력으로 주어진다. 그렇다면 민수가 어떤 카드를 낼지 출력하라. 단, 민수가 카드를 내지 못하는 경우는 없다고 가정한다.

입력

첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000))

다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 다르다.

다음 줄에 K개의 자연수가 주어진다. i번째 수는 철수가 i번째로 내는 카드의 번호이다. 철수가 내는 카드 역시 1 이상 N 이하이다.

출력

K줄에 걸쳐서 수를 출력한다. i번째 줄에는 민수가 i번째로 낼 카드의 번호가 출력되어야 한다.

---

예제 입력 1

10 7 5
2 5 3 7 8 4 9
4 1 1 3 8

예제 출력 1

5
2
3
4
9

출처

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

16566번: 카드 게임

알고리즘 분류

• 자료 구조
• 세그먼트 트리
• 분리 집합

접근 방법

문제가 복잡하게 조건들을 표현하고있는데, 쉽게 생각하자면 주어진 M개의 카드들(각각의 카드 번호는 N을 넘지 않는다) 중 주어진 K개의 숫자보다 크거나 같은 카드를 출력하는 것이다. 단, 이때 이전에 냈던 카드는 못 낸다는 조건이 있다.

먼저, 순서는 문제와 상관이 없기에 parametric search 을 위해 카드를 정렬해도 문제의 답을 구하는데 문제가 없다.

${k}$번째 카드의 번호를 ${A_k}$라고 표현하자. 

 

upper_bound 를 통하여 내부적으로 parametric search 를 이용해준다. 이 후, 다음 탐색에서 동일한 카드를 뽑는 것을 방지하기 위해 여러가지 방법이 있다.

 

가장 Naive하게 생각할 수 있는 방법은 ${A_k}$이 후의 원소를 앞으로 한칸 씩 당겨주는 방법이 있는데 이 경우 O(M), (M은 카드의 수) 이 소요되며 이 경우 전체 복잡도는 O(KM) 이 나오게 되고 ${K \leq 10^4}$ 그리고 ${M \leq 4*10^6}$ 이므로 1.2초안에 문제를 해결 할 수 없다. 

 

이 때 Disjoint Set을 이용하여 이 문제를 상수 시간에 해결하여, O(KlogM)시간내에 해결 할 수 도 있다. [ T(K(logM + 1) ] 

i번째 카드의 대표 원소 ( 해당 카드를 뽑을 수 없는 경우, 다음으로 뽑을 수 있는 카드의 인덱스 ) ( 해당 카드를 뽑을 수 있을 경우, 자신의 인덱스)를 정의하는 p배열을 만들어주자.

p배열의 목적은 "사용한 카드들의 연속된 구간들이 가리키는 다음 카드의 위치"를 O(1)에 찾기 위함이라는 것을 상기하자.

 

만약, 아무런 카드도 뽑히지 않은 초기 상태에서 특정 위치 K에 있는 카드를 뽑게 된다면 p[k] = k+1 을 가리키게 될 것이다.

이러한 과정들이 반복되었을 때 발생하는 문제점을 살펴보자면 k+1카드도 이미 이전에 뽑힌 적이 있던 카드 일 수도 있는데

다음 카드를 찾기 위해 선형탐색을 진행할 필요 없이, Disjoint Set을 통하여 사용되었던 카드의 연속적인 구간을 하나의 집합 단위로 관리하는 것이 효율적이다. 

 

이와 관련된 테크닉은 다음 포스팅에서 다루겠다.

 

find(u) : u이상의 둘 수 있는 위치 k를 찾는 역할

union(u, u+1) : u이상의 둘 수 있는 위치 k를 찾아 카드를 둔 다음, u+1이상의 둘 수 있는 위치와 p[u]를 동기화 하는 역할.

 

이렇게 대표원소가 가리키는 방향은 항상 증가하는 방향이므로, Disjoint Set상에서 Union by rank 방식을 수행하지 않아야하며

O(1)에 가까운 시간복잡도를 위하여 find연산마다 Path Compression을 수행해주어야 한다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
int N, M, K;
int p[4000001], arr[4000001];
int find(int u){
    if( u == p[u] )
        return u;
    return p[u] = find(p[u]);
}
void _union(int u, int v){
    // v = u + 1
    u = find(u), v = find(v);
    if( u == v )
        return ;
    p[u] = v;
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> N >> M >> K;
    for(int i=0; i<M; i++){
        cin >> arr[i];
        p[i] = i;
    }
    sort(arr, arr+M);
    while(K--){
        int upperThan;
        cin >> upperThan;
        int d = find( upper_bound(arr, arr+M, upperThan) - arr );
        cout << arr[d] << '\n';
        _union(d, d+1);
    }
    return 0;
}