[백준 16566] 카드 게임 (C#, C++) - soo:bak

문제 링크

16566번 - 카드 게임

설명

상대가 낸 카드보다 큰 카드 중 가장 작은 것을 내야 하며, 한 번 낸 카드는 다시 쓸 수 없는 게임에 대한 문제입니다. 상대가 낼 카드 K개가 순서대로 주어질 때, 각 라운드에서 내야 할 카드를 구해야 합니다.

접근법

먼저 카드를 정렬하면 이분 탐색으로 조건에 맞는 카드를 빠르게 찾을 수 있습니다.

다음으로 사용한 카드를 처리하는 방법을 생각합니다. 예를 들어 카드가 [2, 5, 7, 9]이고 상대가 3을 내면 5를 냅니다. 이후 상대가 4를 내면 역시 4보다 큰 카드 중 가장 작은 것이 5이지만, 이미 사용했으므로 7을 내야 합니다.

이때 Union-Find를 활용합니다. 5를 사용할 때 5의 위치를 7의 위치와 합쳐둡니다. 나중에 다시 5의 위치를 찾아도 Find 연산으로 바로 7을 얻습니다.

시간 복잡도는 O((M + K) log M)입니다.

---

Code

C#

using System;
using System.Text;

namespace Solution {
  class Program {
    static int[] parent = Array.Empty<int>();
    static int[] cards = Array.Empty<int>();

    static int Find(int x) {
      if (parent[x] == x)
        return x;
      parent[x] = Find(parent[x]);
      return parent[x];
    }

    static void Union(int a, int b) {
      a = Find(a);
      b = Find(b);
      if (a != b)
        parent[a] = b;
    }

    static int UpperBound(int[] arr, int len, int value) {
      var lo = 0;
      var hi = len;
      while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (arr[mid] <= value)
          lo = mid + 1;
        else
          hi = mid;
      }
      return lo;
    }

    static void Main(string[] args) {
      var first = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      var n = first[0];
      var m = first[1];
      var k = first[2];

      cards = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      Array.Sort(cards, 0, m);

      parent = new int[m + 1];
      for (var i = 0; i <= m; i++)
        parent[i] = i;

      var output = new StringBuilder();
      var query = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      for (var i = 0; i < k; i++) {
        var x = query[i];
        var idx = UpperBound(cards, m, x);
        idx = Find(idx);
        output.Append(cards[idx]).Append('\n');
        Union(idx, idx + 1);
      }

      Console.Write(output.ToString());
    }
  }
}

C++

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

typedef vector<int> vi;

vi parent;
vi cards;

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

void Union(int a, int b) {
  a = Find(a);
  b = Find(b);
  if (a != b)
    parent[a] = b;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, M, K; cin >> N >> M >> K;
  cards.resize(M);
  for (int i = 0; i < M; i++)
    cin >> cards[i];
  sort(cards.begin(), cards.end());

  parent.resize(M + 1);
  for (int i = 0; i <= M; i++)
    parent[i] = i;

  ostringstream out;
  for (int i = 0; i < K; i++) {
    int x; cin >> x;
    int idx = upper_bound(cards.begin(), cards.end(), x) - cards.begin();
    idx = Find(idx);
    out << cards[idx] << "\n";
    Union(idx, idx + 1);
  }

  cout << out.str();

  return 0;
}