서강대학교 2018 Sogang Programming Contest (Master) 기출문제

문제

철수와 민수는 카드 게임을 즐겨한다. 이 카드 게임의 규칙은 다음과 같다.

N개의 빨간색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 M개의 카드를 고른다.
N개의 파란색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 빨간색에서 고른 번호와 같은 파란색 카드 M개를 고른다. 철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다.
철수와 민수는 고른 카드 중에 1장을 뒤집어진 상태로 낸다. 그리고 카드를 다시 뒤집어서 번호가 큰 사람이 이긴다. 이 동작을 K번 해서 더 많이 이긴 사람이 최종적으로 승리한다. 한 번 낸 카드는 반드시 버려야 한다.
철수는 뛰어난 마술사이기 때문에 본인이 낼 카드를 마음대로 조작할 수 있다. 즉, 카드를 버리고 민수 몰래 다시 들고 온다거나 민수한테 없는 카드를 내기도 한다.

민수는 뛰어난 심리학자이기 때문에 철수가 낼 카드를 알아낼 수 있다. 그래서 민수는 철수가 낼 카드보다 큰 카드가 있다면 그 카드들 중 가장 작은 카드를 내기로 했다.

K번 동안 철수가 낼 카드가 입력으로 주어진다. 그렇다면 민수가 어떤 카드를 낼지 출력하라. 단, 민수가 카드를 내지 못하는 경우는 없다고 가정한다.

입력

첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000))

다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 다르다.

다음 줄에 K개의 자연수가 주어진다. i번째 수는 철수가 i번째로 내는 카드의 번호이다. 철수가 내는 카드 역시 1 이상 N 이하이다.

출력

K줄에 걸쳐서 수를 출력한다. i번째 줄에는 민수가 i번째로 낼 카드의 번호가 출력되어야 한다.

접근 과정

민수가 가지고 있는 카드 중에서 철수가 낸 카드보다 큰 것 중 가장 작은 것을 하나씩 골라내야 하는 문제이다. 처음에는 그리디 방식을 통해 접근하였다. 민수가 가진 카드와 철수가 낸 카드를 정렬한 뒤 작은 값부터 비교해가며 민수가 내야 할 카드를 매칭하는 방식이다.
위 알고리즘에는 한 가지 문제가 있었는데 철수가 낸 카드가 정렬에 따라 순서가 뒤섞이다 보니 먼저 냈던 카드의 최적값이 먼저 비교된 작은 값에 뺏겨버리는 경우가 생겼다.
민수가 가지는 카드 M은 최대 4백만, 철수가 낸 카드 수 K도 최대 1만이므로 \(O(MK)\)로 최적값을 일일이 찾아보기엔 그 수가 너무 많다. 그래서 선형탐색보다 빠른 탐색 알고리즘을 고민해보니 이분탐색을 통해 빠르게 최적해를 구할 수 있다는 생각이 들었다. (시간복잡도 \(O(\log M)\))
문제는 동일한 카드는 한 번만 낼 수 있었기에 이분탐색만으로 선택했던 카드를 제외한 최적해를 찾기는 쉽지 않아 보였다. 그래서 생각한 것이 선택했던 카드를 기록하고 이분 탐색을 통해 찾은 최적해를 기준으로 선택하지 않은 최적의 카드를 무작정 찾아보는 것이었다. 최적해를 기준으로 선형탐색을 시작하면 적어도 K번 안으로 최적의 카드를 고를 수 있다. (시간복잡도 \(O(\log M + K)\))
이제 최적의 카드를 고르길 K번 반복하게 되면 시간 복잡도는 결과적으로 \(O(K^{2})\)이 된다. K만 따졌을 때 대략적인 연산 횟수가 1천만 회이므로 통과할 수 있을 것으로 보였다. 다행히 800ms로 제한 시간 1초보다 빨리 실행되어 통과할 수 있었다. 입출력이나 정렬 등 K 외의 연산에서 추가로 시간을 소비한 것으로 보인다. 1등은 무려 140ms…
이 문제는 이분탐색 이외에도 유니온 파인드, 세그먼트 트리 등을 이용하여 풀 수 있다고 한다. 본인의 풀이가 일반적이지 않았던 모양이다. 이 중 서로소 집한들의 합집합을 구하는 유니온 파인드 알고리즘은 이번에 처음 접해보았는데 이번과 문제에 해당 알고리즘을 적용하여 풀 수 있다는 사실이 놀라웠다. 아무리 공부해도 새로운 내용이 계속 나오는 것 같다 ㅋㅋ

소스 코드

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

int main() {
    int N, M, K;
    vector<int> chulCard, minCard, result;

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M >> K;
    
    minCard.resize(M);
    for (int i = 0; i < M; ++i) {
        cin >> minCard[i];
    }

    chulCard.resize(K);
    for (int i = 0; i < K; ++i) {
        cin >> chulCard[i];
    }

    sort(minCard.begin(), minCard.end());

    // 이분탐색 후 선형탐색
    vector<bool> bChecked(M, false);
    result.resize(K);
    for (int i = 0; i < K; ++i) {
        int optimalIndex = M - 1;
        int card = chulCard[i];
        int l = 0;
        int r = M - 1;
        
        // 이분 탐색을 통해 처음 받은 카드 중 최적의 카드를 뽑음
        while (l <= r) {
            int mid = (l + r) / 2;

            if (minCard[mid] > card) {
                r = mid - 1;
                if (minCard[mid] < minCard[optimalIndex]) { optimalIndex = mid; }
            } else {
                l = mid + 1;
            }
        }

        // 최적 카드 값을 시작으로 뽑지 않은 카드를 탐색
        while (bChecked[optimalIndex] && optimalIndex < M) { ++optimalIndex; }
        bChecked[optimalIndex] = true;
        result[i] = minCard[optimalIndex];
    }


    for (int i = 0; i < K; ++i) {
        cout << result[i] << '\n';
    }
    return 0;
}


/* 첫 풀이 그리디
    // vector<pair<int, int> > chulCard;
    //        {카드번호, 순서 색인}
    sort(chulCard.begin(), chulCard.end());

    result.resize(K);
    int minIdx = 0;
    for (int i = 0; i < K; ++i) {
        while (minCard[minIdx] <= chulCard[i].first) { ++minIdx; }
        result[chulCard[i].second] = minCard[minIdx++];
    }
*/