[백준 / BOJ] C++ 16566 카드 게임

16566번: 카드 게임

 

문제

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

16566번: 카드 게임

 

 

풀이

철수가 낸 카드보다 숫자가 큰 카드 중 가장 작은 카드를 민수가 내도록 하면 된다. 즉, 사용할 수 있는 카드를 오름차순 정렬한 다음 upper_bound 함수를 사용하면 된다. (upper_bound 함수는 찾고자 하는 값을 초과하는 값 중 가장 작은 값의 iterator를 반환한다.) 그러나 같은 카드는 한 번만 사용할 수 있기 때문에 같은 카드를 선택해야 할 때, 다음 카드를 선택하도록 해야 한다.

 

처음에는 방문처리를 해보기도 하고 매 연산마다 사용한 카드를 -1로 바꾸고 정렬도 해봤다. 그러나 모두 TLE를 받았다. 해결 방법은 유니온 파인드 알고리즘을 사용해 그룹핑을 해주는 것이다.

 

 

예를 들어 [2, 3, 4, 5, 7] 의 카드를 민수가 사용할 수 있을 때, 철수가 0을 낸다면 upper_bound 함수는 2를 반환할 것이다. 그러면 2는 이미 사용된 카드가 되어 [2, 3, 4, 5, 7] 가 된다. 다음번에 다시 철수가 0을 낸다면 upper_bound 함수는 또 다시 2를 반환할 것이다. 하지만 우리는 바로 다음 카드인 3을 사용해야 한다.

 

바로 이때 upper_bound가 반환한 2가 3을 가리키도록 하기 위해 유니온 파인드 알고리즘을 사용한다. 맨 처음 철수가 0을 낼 때 upper_bound가 2를 반환하면 2를 출력하고 2와 바로 다음 수인 3을 union 해준다. 이때 보통과 다른 점은 parent는 큰 수를 가리키도록 한다. 그러면 [[2, 3], 4, 5, 7] 가 되어 2는 3을 가리키고 있으므로 다음 번에 철수가 0을 내어 upper_bound가 2를 반환하더라도 우리는 find 함수를 통해 3을 가리키고 있음을 알 수 있다. 단, 유니온 파인드 알고리즘을 사용할 때 기준은 다음 원소를 참조하기 편한 인덱스이다.

 

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> p;

int find(int x) {
  if (p[x] != x)
    p[x] = find(p[x]);
  return p[x];
}

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if (x < y)
    p[x] = y;
  else
    p[y] = x;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M, K;
  cin >> N >> M >> K;
  p.resize(N + 1);
  iota(p.begin(), p.end(), 0);
  vector<int> c(M);
  for (int i = 0; i < M; i++)
    cin >> c[i];
  sort(c.begin(), c.end());
  while (K--) {
    int x;
    cin >> x;
    int idx = find(upper_bound(c.begin(), c.end(), x) - c.begin());
    cout << c[idx] << '\n';
    merge(idx, idx + 1);
  }
  return 0;
}