이번 문제는 백준의 골드 5 문제 멀티버스 II이다.
문제를 한 번 차근차근 읽어보도록 하자.
최대 100개의 우주가 주어질 때, 아래의 조건을 검사한다.
위의 조건을 만족하는 우주는 서로 균등하다고 한다.
주어진 우주 중에서 균등한 우주 쌍의 수를 구하는 문제이다.
하나의 우주에는 최대 10000개의 행성이 존재할 수 있다.
문제를 어떤 식으로 풀어야 할까?
완전 탐색?
우선 문제에 주어진 조건을 보아하니, 비교를 해야할 것 같다.
그럼 전체 우주를 다 비교해서 쌍을 구해야 할까?
그럼 O(N^2)의 시간으로 최대 100 * 10000개를 검사한다.
말도 안되게 큰 시간이 소요되므로, 완전탐색은 불가능하다.
우선 100개의 우주가 주어진다면, 100개의 우주는 모두 검사해야 한다.
그럼 관건은 각 우주를 어떻게 빠르게 검사할 것인지가 된다.
좌표 압축
이전에 푼 문제 중 좌표 압축과 관련된 문제가 있었다.
해당 개념이 문득 떠올랐다.
좌표 압축이란 배열의 각 원소들을 대소에 따라 값을 압축하는 것이다.
예를 들어, {4, 1, 0, -1, 5} 라는 배열이 있다고 생각해보자.
좌표를 압축하면 {5, 2, 1, 0, 6}이 되는 것이다.
그럼 {18, 15, 14, 13, 19}는 어떨까?
압축 했을때 {5, 2, 1, 0, 6}으로 동일하게 압축됨을 알 수 있다.
이 점을 이용하면 빠르게 문제를 풀 수 있을 것 같다!
첫 구현은 아래와 같았다.
int num = 0, planet_num = 0;
int multiverse[100][10000];
vector<string> string_verse;
void compress_coordinate() {
for (int i = 0; i < num; i++) {
set<int> max_heap;
for (int j = 0; j < planet_num; j++) {
cin >> multiverse[i][j];
max_heap.insert(multiverse[i][j]);
}
string temp = "";
for (int j = 0; j < planet_num; j++) {
auto idx = max_heap.find(multiverse[i][j]);
temp += to_string(distance(max_heap.begin(), idx));
}
string_verse.push_back(temp);
}
}
bool check_compressed_coordinate(string src, string dest) {
if (src != dest)
return false;
return true;
}
int main() {
cin >> num >> planet_num;
compress_coordinate();
int answer = 0;
for (int i = 0; i < num - 1; i++)
for (int j = i + 1; j < num; j++)
if (check_compressed_coordinate(string_verse[i], string_verse[j]))
answer++;
cout << answer;
return 0;
}하지만 이 방식은 시간 초과를 받게 되었다.
이전에 좌표 압축 문제를 풀 때 set을 이용 했었기 때문에
동일하게 set을 이용하고 distance 함수를 이용했다.
내 생각에는 set을 이용하는 데에서 시간이 오래걸린 것 같다.
이분 탐색
내가 사용한 자료구조와 함수들의 시간 복잡도에 대해 조금 공부해보았다.
찾아보니 distance 함수를 통해 함수의 위치를 찾는 로직은
find와 함께 사용하면 O(N)의 시간 복잡도를 갖는다고 한다.
이 부분에서 아마 시간 초과가 발생한 것 같다.
lower_bound
set에서는 distance 없이 iterator를 int형으로 바꿀 수 없다.
따라서 아예 vector 자료구조를 사용하도록 변경하기로 했다.
vector 자료구조에 값을 받은 뒤, 정렬하고 중복을 제거하도록 한다.
algorithm 헤더의 sort를 통해서 정렬을 할 수 있다.
또한 동일한 헤더의 unique를 통해서 중복된 값을 제거할 수 있다.
이후 lower_bound 함수를 통해서 해당 값의 압축된 좌표를 반환한다.
lower_bound는 대상 값 이상의 값이 발견되는 위치를 반환한다.
따라서 정렬된 배열에 대해서는 좌표 압축이 가능한 것이다.
또한 vector.begin()과의 차연산을 통해 int로 변환이 가능하다.
이를 이용해서 최종적으로 아래와 같이 구현하였다.
int num = 0, planet_num = 0;
int multiverse[100][10000];
void compress_coordinate() {
for (int i = 0; i < num; i++) {
vector<int> max_heap;
for (int j = 0; j < planet_num; j++) {
cin >> multiverse[i][j];
max_heap.push_back(multiverse[i][j]);
}
sort(max_heap.begin(), max_heap.end());
max_heap.erase(unique(max_heap.begin(), max_heap.end()), max_heap.end());
for (int j = 0; j < planet_num; j++) {
int idx = lower_bound(max_heap.begin(), max_heap.end(), multiverse[i][j]) - max_heap.begin();
multiverse[i][j] = idx;
}
}
}
bool check_compressed_coordinate(int src, int dest) {
for (int i = 0; i < planet_num; i++) {
if (multiverse[src][i] != multiverse[dest][i])
return false;
}
return true;
}
int main() {
cin >> num >> planet_num;
compress_coordinate();
int answer = 0;
for (int i = 0; i < num - 1; i++)
for (int j = i + 1; j < num; j++)
if (check_compressed_coordinate(i, j))
answer++;
cout << answer;
return 0;
}Appendix : unique
algorithm 헤더에서 사용할 수 있는 unique 함수이다.
해당 함수는 굉장히 특이한 동작을 하는 함수이다.
vector나 배열의 범위가 매개변수로 들어가게 되며,
주어진 범위 내에서 중복된 값을 삭제하고 배열을 재배치한다.
단, 배열의 크기가 줄어들지는 않고 남은 자리는 원래 값이 들어간다.
예를 들어, 1 1 2 3 3 4 5 5 5 6과 같은 배열이 있을 때
unique 함수를 사용하면, 1 2 3 4 5 6 5 5 5 6이 된다.
이제 우리는 erase 함수를 통해 뒷 부분만 삭제하면?
1 2 3 4 5 6과 같이 중복이 제거된 배열을 얻을 수 있는 것이다.
unique 함수의 동작이 종료되면, 해당 위치 뒤의 iterator가 반환된다.
따라서 erase(unique(begin, end), end)와 같이 사용하면 된다.
C++로 알고리즘 문제를 풀 때, STL은 굉장히 중요하다.
이 문제처럼 STL의 내장 함수를 유연하게 다룰 수 있다면,
문제를 푸는 속도와 코드의 간결함이 훨씬 깔끔해진다.
자료구조와 내장 함수에 대해서 조금 더 공부해봐야겠다.