[Algorithm]Baekjoon 16566 :: 카드 게임

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

16566번: 카드 게임

 
 
using namespace std;
 
 
int n, m, k;
int minsuCards[4000001] = { 0 };
int parents[4000001] = { 0 };
 
 
int getParent(int node)
{
    if (node == parents[node]) return node;
    return parents[node] = getParent(parents[node]);
}
 
void unionParents(int a, int b)
{
    a = getParent(a);
    b = getParent(b);
 
    if (a > b) parents[b] = a;
    else parents[a] = b;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m >> k;
 
    for (int i = 0; i < m; ++i)
    {
        cin >> minsuCards[i];
        parents[i] = i;
    }
 
    sort(minsuCards, minsuCards + m);
 
    for (int i = 0; i < k; ++i)
    {
        int input;
        cin >> input;
 
        int index = upper_bound(minsuCards, minsuCards + m, input) - minsuCards;
        index = getParent(index);
        printf("%d \n", minsuCards[index]);
 
        unionParents(parents[index], parents[index] + 1);
    }
 
}
 

 

플레5문제였지만, 최근에 비슷한 유형의 '공항'이란 문제를 풀었었기 때문에 굉장히 쉽게 풀었다.

문제 설명은 뭔가 길고 복잡하지만, 사실 매우 간단하다.

 

주어진 숫자보다 '큰 수중에서 가장 작은값'을 찾아서 출력하면 되는데, 해당 숫자는 출력 후 버려야한다. 

즉, 이후에 '큰 수중에서 가장 작은 값'을 찾는 과정에 이전에 출력했던 숫자들은 있으면 안된다.

 

단순히 특정 수보다 큰 수를 찾는거면 upper_bound를 사용해서 logN번으로 찾기가 가능하다. (물론 이전에 오름차순 정렬을 해놔야한다).

근데 한번 출력한 수는 버려야한다. 그래서 upper_bound로 찾은 값이 만약 버린수일 경우,

'해당 숫자보다 오른쪽에서 가장 가까운 버리지 않은 수' 를 찾아야 한다.

 

이 가장 가까운 버리지 않은 수를 찾기 위해 그냥 하나씩 접근해서 한다고 치면, 당연히 시간초과다.

한번에 알아내는 과정이 필요한데 그게 바로 Union-Find이다.

특정숫자를 찾아내서 출력 후, 특정숫자의 인덱스와 해당인덱스 +1을 union 한다. 즉 하나의 집합으로 합친다.

그러면 자연스럽게 해당숫자 인덱스의 부모는 그다음 숫자의 인덱스를 가리키기 때문에, 이후 upper_bound의 index값이 똑같은값이 나오더라도, 해당인덱스의 부모를 바로 가리키기 때문에 해당 인덱스의 숫자를 출력해주면 된다.

 

유의해야할 점은, 큰수를 찾아야하기 때문에 parents를 업데이트 할 때 큰수가 부모가 되게해야한다.

위 로직을 잘 이해했다면 당연히 그렇게 하겠지만, 이해를 못하고 무작정 Union-Find인갑다 하고 대입하려하면 당연히 틀린다.