BOJ 16566 카드 게임 [C++]

규칙이 길고 복잡해 보이지만, 사실 별거 없는 문제다.

규칙에서 문제 풀이에 필요한 정보만 추출해내면,

 

철수는 1~N까지 숫자가 적힌 카드중 아무거나 낼 수 있다.

민수는 철수의 카드보다 큰 숫자가 적힌 카드를 내야한다.

 

문제 입력은 첫째줄에 n, m(민수 카드 개수), k(철수가 내는 카드 개수)가 주어지고

둘째줄에 민수의 카드, 셋째줄에 철수의 카드가 주어진다.

출력은 철수의 각각 카드에 대한 것이므로 k개 줄에 걸친다.

 

민수의 카드중 철수의 특정 카드보다 큰 카드를 파악하기 위해서는 먼저 민수 카드의 배열을 정렬해야한다.

그리고 철수 카드보다 큰 카드의 위치를 알려줄 것인데, 이때는 앞에서부터 차례대로 탐색하는 방법이 있지만 이는 시간복잡도가 최대 O(M)에 달할 수 있어 비효율적이다.

따라서 이분탐색을 이용해 민수 카드 벡터에서 특정 값을 초과하는 원소가 나타나는 최초 인덱스를 반환하는

upper_bound함수를 사용하였다. 이 함수는 이분탐색을 이용해 시간복잡도가 O(lg M)밖에 되지 않는다.

 

또 민수에게서 이미 사용한 카드를 또 사용할 순 없다. 그래서 카드를 버리는 것을 구현해야한다.

하지만 벡터에서 원소를 삭제하는 것은 매우 비효율적이고 그렇다고 리스트를 사용하면 upper_bound 함수를 사용하지 못하므로(아마?) 이미 사용한 카드(의 인덱스)는 visited 벡터를 이용해 방문(사용)처리 해주는 것을 이용했다.

while (visited[key]) key++; 은 현재 가리키는 카드(의 인덱스)가 사용된 카드(의 인덱스)라면 사용되지 않은 카드(의 인덱스)가 나올때까지 다음 인덱스로 넘어가는 것을 의미한다.

 

그렇게 사용가능한 카드가 있으면 출력하고 그 인덱스를 방문처리한다.

 

아래는 800ms로 통과한 코드이다.

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

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

    int n, m, k,buf;
    cin >> n >> m >> k;

    vector<int> minsu(m), ahn(k);
    vector<bool> visited(m, false);

    for (int i = 0; i < m; i++) {
        cin >> minsu[i];
    }

    sort(minsu.begin(), minsu.end());
    
    for (int i = 0; i < k; i++) {
        cin >> buf;
        int key = upper_bound(minsu.begin(), minsu.end(), buf) - minsu.begin();
        while (visited[key]) key++;

        cout << minsu[key] << "\n";
        visited[key] = true;
    }

    return 0;

}