📖 백준 16566번 : https://www.acmicpc.net/problem/16566
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 1.2 초 | 512 MB |
문제
철수와 민수는 카드 게임을 즐겨한다. 이 카드 게임의 규칙은 다음과 같다.
-
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번째로 낼 카드의 번호가 출력되어야 한다.
풀이
문제의 의도는 이분 탐색과 Union-Find를 활용해서 푸는 것이다. 하지만 시간 복잡도를 계산해보면 단순하게 자료구조를 잘 사용하는 것으로 풀릴 것 같았다. 처음에 set을 사용해서 입력을 받음과 동시에 insert해주고 값을 upper_bound로 찾고 erase해주는 방식으로는 시간 초과를 받았다. 하지만 O(logN)의 복잡도를 가지는 set이기 때문에 조금만 다듬으면 통과할 수 있을 것 같다는 가능성을 보았다.
입력을 받을 때 배열에 입력을 받고 STL sort를 사용해서 정렬한 값을 set에 집어넣는 방식으로 입력받는 시간을 줄였다. set에 입력하는 시간은 O(logN)이므로 차이가 없어 보이지만, 입력을 받고 size를 조정하고 메모리를 추가로 할당하는 과정에서 이론보다 조금 더 시간이 걸린다. 배열로 입력을 받는 것보다 vector로 push_back하는 과정에서 더 시간이 오래 걸리는 것과 유사하다. 그리고 STL sort가 매우 잘 짜여져 있기 때문에 모든 원소를 set을 이용해서 정렬하는 것보다 더 빠르다.
1.2초라는 다소 애매한 시간 제한이 이러한 꼼수를 막기위한 장치로 보였지만 앞서 말한 방식으로 구현하면 1000ms로 풀린다!
코드
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int arr[4000000];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int temp;
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < m; i++) cin >> arr[i];
sort(arr, arr + m);
set<int> card(arr, arr + m);
for (int i = 0; i < k; i++) {
cin >> temp;
auto it = card.upper_bound(temp);
cout << *it << '\n';
card.erase(it);
}
return 0;
}