백준 16566번
오늘 풀어본 문제는 백준의 16566번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
철수와 민수는 카드 게임을 즐겨한다. 이 카드 게임의 규칙은 다음과 같다.
-
$N$ 개의 빨간색 카드가 있다. 각각의 카드는 순서대로 $1$ 부터 $N$ 까지 번호가 매겨져 있다. 이 중에서 $M$ 개의 카드를 고른다.
-
$N$ 개의 파란색 카드가 있다. 각각의 카드는 순서대로 $1$ 부터 $N$ 까지 번호가 매겨져 있다. 이 중에서 빨간색에서 고른 번호와 같은 파란색 카드 $M$ 개를 고른다.
-
철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다.
-
철수와 민수는 고른 카드 중에 $1$ 장을 뒤집어진 상태로 낸다. 그리고 카드를 다시 뒤집어서 번호가 큰 사람이 이긴다. 이 동작을 $K$ 번 해서 더 많이 이긴 사람이 최종적으로 승리한다. 한 번 낸 카드는 반드시 버려야 한다.
철수는 뛰어난 마술사이기 때문에 본인이 낼 카드를 마음대로 조작할 수 있다. 즉, 카드를 버리고 민수 몰래 다시 들고 온다거나 민수한테 없는 카드를 내기도 한다.
민수는 뛰어난 심리학자이기 때문에 철수가 낼 카드를 알아낼 수 있다. 그래서 민수는 철수가 낼 카드보다 큰 카드가 있다면 그 카드들 중 가장 작은 카드를 내기로 했다.
$K$ 번 동안 철수가 낼 카드가 입력으로 주어진다. 그렇다면 민수가 어떤 카드를 낼지 출력하라. 단, 민수가 카드를 내지 못하는 경우는 없다고 가정한다.
입력
첫째 줄에 세 개의 자연수 $N$, $M$, $K$ 가 주어진다. $(1 \le M \le N \le 4,000,000, 1 \le K \le \min (M, 10,000))$
다음 줄에 카드의 번호를 나타내는 $M$ 개의 자연수가 주어진다. 각각의 수들은 $1$ 이상이고 $N$ 이하이며 서로 다르다.
다음 줄에 $K$ 개의 자연수가 주어진다. $i$ 번째 수는 철수가 $i$ 번째로 내는 카드의 번호이다. 철수가 내는 카드 역시 $1$ 이상 $N$ 이하이다.
출력
$K$ 줄에 걸쳐서 수를 출력한다. $i$ 번째 줄에는 민수가 $i$ 번째로 낼 카드의 번호가 출력되어야 한다.
풀이과정
1번째 시도
문제를 보고 카드를 정렬한 뒤 이분 탐색을 이용하여 철수가 낼 카드보다 큰 카드를 찾고 낸 뒤, 그 카드를 없애는 방식을 생각해보았다. 삭제 시간도 최소한으로 하기 위해서 일반 벡터보다 시간복잡도가 더 낮은 set 을 이용하기로 하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, M, K;
cin >> N >> M >> K;
set<int> myCards;
vector<int> enemyCards;
for (int i=0; i<M; i++) {
int temp;
cin >> temp;
myCards.insert(temp);
}
for (int i=0; i<K; i++) {
int temp;
cin >> temp;
enemyCards.emplace_back(temp);
}
for (auto& card : enemyCards) {
auto myCard = myCards.upper_bound(card);
cout << *myCard << "\n";
myCards.erase(myCard);
}
return 0;
}
실행 결과 ‘시간 초과’ 가 떴다.
2번째 시도
시간 초과의 원인으로 알아낸 것은, set 의 삽입과 삭제의 시간복잡도의 ‘상수’ 였다. set 은 레드-블랙 트리로 구현되어 있기 때문에 자동으로 밸런싱이 일어나는데, 이것으로 인해 상수가 늘어나게 된다.
테스트 케이스 중에 이를 활용해서 시간 초과를 발생시키는 경우도 있는 것 같아, 들어오는 카드들을 한 번 섞어 준뒤 set 에 넣는 것을 시도해보았다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, M, K;
cin >> N >> M >> K;
vector<int> tempMyCards;
set<int> myCards;
vector<int> enemyCards;
for (int i = 0; i < M; i++) {
int temp;
cin >> temp;
tempMyCards.push_back(temp);
}
for (int i=0; i<K; i++) {
int temp;
cin >> temp;
enemyCards.emplace_back(temp);
}
random_device rd;
mt19937 g(rd());
shuffle(tempMyCards.begin(), tempMyCards.end(), g);
for (auto& card : tempMyCards) {
myCards.insert(card);
}
for (int i=0; i<M; i++) {
int temp;
cin >> temp;
myCards.insert(temp);
}
for (auto& card : enemyCards) {
auto myCard = myCards.upper_bound(card);
cout << *myCard << "\n";
myCards.erase(myCard);
}
return 0;
}
실행 결과 ‘시간 초과’ 가 떴다.
3번째 시도
결국 set 을 쓰지 않고 문제를 해결해보기로 했다. 가장 먼저 떠올린 방법은
삭제에 시간이 오래 걸린다면, 삭제를 하지 않으면 되는 것 아닌가?
라는 생각이었고, 현재 카드의 값을 다음 카드의 값으로 바꾸는 방식을 통해, 사실상 삭제와 동일한 효과를 내기를 기대하며 코드를 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, M, K;
cin >> N >> M >> K;
vector<int> myCards;
vector<int> enemyCards;
int temp;
for (int i=0; i<M; i++) {
cin >> temp;
myCards.emplace_back(temp);
}
myCards.emplace_back(temp);
for (int i=0; i<K; i++) {
cin >> temp;
enemyCards.emplace_back(temp);
}
sort(myCards.begin(), myCards.end());
for (auto& card : enemyCards) {
int myCardIndex = upper_bound(myCards.begin(), myCards.end(), card) - myCards.begin();
cout << myCards[myCardIndex] << "\n";
myCards[myCardIndex]= myCards[myCardIndex + 1];
}
return 0;
}
실행 결과 ‘틀렸습니다’ 가 떴다.
4, 5번째 시도
틀린 원인으로 알아낸 것은 뒤의 카드로 대체하는 과정에서 여러 번 사용할 수 있는 카드가 생기게 될 수 있는 것이었다.
카드 $A, B, C$ 가 오름차순으로 나열되어 있다고 생각해보자.
$A$ 가 사용되어 값이 $B$ 로 대체된 후, $B$ 가 다시 사용되었을 때 값이 $C$ 로 대체되었다고 하자. $A$ 가 $B$ 의 원래 값을 가지고 있고 $B$ 는 $C$ 의 값으로 변경된 상태인 것이다. 이때, $A$ 를 사용함으로써 $B$ 가 원래 가지고 있던 값을 다시 사용할 수 있게 되는 것이 문제점이였다.
이를 해결하기 위해 사용한 것은 Union-Find 였다. 이미 사용된 카드를 다음 카드와 Union 하고, 카드를 찾을 때는 해당 그룹에서 가장 큰 카드를 찾도록 하였다.
기존에 만들어두었던 DisjointSet 클래스를 살짝 개조하여 사용하였다.
코드는 다음과 같이 수정하였다.
disjoint_set.hpp
#ifndef __DISJOINT_SET_HPP__
#define __DISJOINT_SET_HPP__
#include <vector>
class DisjointSet {
private:
std::vector<int> parent;
public:
DisjointSet(int n) {
parent.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int u) {
if (u == parent[u]) {
return u;
}
else {
return parent[u] = find(parent[u]);
}
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u > v) {
parent[v] = u;
}
else if (u < v) {
parent[u] = v;
}
}
};
#endif // !__DISJOINT_SET_HPP__
main.cpp
#include <bits/stdc++.h>
#include "disjoint_set.hpp"
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, M, K;
cin >> N >> M >> K;
vector<int> myCards;
vector<int> enemyCards;
DisjointSet diset(4000001);
for (int i=0; i<M; i++) {
int temp;
cin >> temp;
myCards.emplace_back(temp);
}
for (int i=0; i<K; i++) {
int temp;
cin >> temp;
enemyCards.emplace_back(temp);
}
sort(myCards.begin(), myCards.end());
for (auto& card : enemyCards) {
int myCardIndex = upper_bound(myCards.begin(), myCards.end(), card) - myCards.begin();
cout << myCards[diset.find(myCardIndex)] << "\n";
diset.merge(myCardIndex, myCardIndex + 1);
}
return 0;
}
4번째 시도에서는 헤더 파일의 코드를 제출에 포함시키지 않은 것이 문제가 되어 ‘컴파일 에러’ 가 발생하였고, 5번째 시도에서는 실행 결과 ‘틀렸습니다’ 가 떴다.
6번째 시도
틀린 원인으로 알아낸 것은, 인덱스를 Union 하는 과정에서 가장 큰 값의 인덱스가 아닌 찾아진 값의 인덱스를 Union 하는데 사용해 버린 것이다.
예를 들면 내 카드가 $10$, $20$, $30$ 이라고 할 때, 입력으로 $5$, $7$ 이 들어오면 처음에 $5$ 에 대항하여 $10$ 을 내면 $10$ 과 $20$ 이 제대로 합쳐지지만, $7$ 에 대항한 카드를 찾는 과정에서 발견된 ‘인덱스’ 는 $10$ 의 인덱스이고, find 를 통해 찾은 카드는 $20$ 이 된다.
카드를 내는 것은 제대로 이루어지지만, Union 과정에서 이미 합쳐져 있는 $10$ 과 $20$ 카드의 인덱스를 또 합치려고 하는데, 우리가 의도한 것은 $20$ 과 다음 카드인 $30$ 의 인덱스를 합치는 것이기 때문에 문제가 발생한다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
#ifndef __DISJOINT_SET_HPP__
#define __DISJOINT_SET_HPP__
#include <vector>
class DisjointSet {
private:
std::vector<int> parent;
public:
DisjointSet(int n) {
parent.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int u) {
if (u == parent[u]) {
return u;
}
else {
return parent[u] = find(parent[u]);
}
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u > v) {
parent[v] = u;
}
else if (u < v) {
parent[u] = v;
}
}
};
#endif // !__DISJOINT_SET_HPP__
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, M, K;
cin >> N >> M >> K;
vector<int> myCards;
vector<int> enemyCards;
DisjointSet diset(4000001);
for (int i=0; i<M; i++) {
int temp;
cin >> temp;
myCards.emplace_back(temp);
}
for (int i=0; i<K; i++) {
int temp;
cin >> temp;
enemyCards.emplace_back(temp);
}
sort(myCards.begin(), myCards.end());
for (auto& card : enemyCards) {
int myCardIndex = diset.find(upper_bound(myCards.begin(), myCards.end(), card) - myCards.begin());
cout << myCards[myCardIndex] << "\n";
diset.merge(myCardIndex, myCardIndex + 1);
}
return 0;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
역시 CLASS 5 문제다! 좀 할만한가 싶더니 플래 문제들로 뚜들겨 맞고 있다… 아직도 플래티넘 문제가 3개나 남아있는데, 대체 무슨 고난과 역경이 나를 맞이할 것인가?
그래도 오늘 문제는 배울 점이 꽤 많았던 것 같다. set 은 느리다는 것과, Union-Find 를 이렇게 활용할 수도 있다는 것, 그리고 헤더파일 코드도 제대로 붙여넣기를 해서 제출해야 한다는 것까지도 말이다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/16566