[백준] 16566.cpp : 카드 게임

www.acmicpc.net/problem/16566

16566번: 카드 게임

---

• 문제가 복잡해보이지만, 분석하고 보면 간단한 문제이다.
• 주어진 값보다 큰 값들 중 가장 작은 값(정렬 후 바로 오른쪽에 있는 값)
• 주어지는 값에 중복이 있을 수 있기 때문에, 만약 그 전에 이미 출력했던 값일 경우는 제외하고 생각한다.
• 없는 값이 주어질 수도 있기 때문에, 이진 탐색에서 해당 부분까지 고려해주면 문제 될 것이 없다.
• 더욱 간단하게는 algorithm 에서 제공하는 upper_bound 를 활용하면 된다.

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, k;

int binfind(const vector<int>& v, int key)          // 해당 값을 이진탐색
{
    int start = 0;
    int end = v.size() - 1;
    int mid = 0;

    while(start <= end)
    {
        mid = (start + end) / 2;

        if(v[mid] == key)     return mid;           // 만약 존재한다면 해당 인덱스를 반환하고
        else if(v[mid] > key) end = mid - 1;
        else                  start = mid + 1;
    }

    return mid - 1;                                 // 존재하지 않는다면 해당 인덱스 직전 값을 반환한다
}

int main(void)
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> n >> m >> k;

    vector<int> v(m);                           // 가지고 있는 카드들
    vector<bool> v2(m, false);                  // 해당 카드를 냈었는지 안 냈었는지 확인용
    for(int i = 0 ; i < m ; i++)
    {
        cin >> v[i];
    }
    sort(v.begin(), v.end());

    vector<int> out(k);
    for(int i = 0 ; i < k ; i++)                // 철수가 낼 카드 순서
    {
        cin >> out[i];
    }
    for(int i = 0 ; i < k ; i++)
    {
        for(int idx = binfind(v, out[i]) + 1 ; idx < v.size() ; idx++)  // 철수가 내는 값을 찾아보고, 해당 값의 다음 카드부터 탐색
        {
            if(v2[idx] == false)                // 내가 내지 않았던 카드들 중에 가장 작은 카드
            {
                v2[idx] = true;                 // 냈다고 표시
                cout << v[idx] << '\n';
                break;
            }
        }
    }
}