[알고리즘] C++ 백준 18869 멀티버스 Ⅱ(좌표 압축)

백준 18869

https://www.acmicpc.net/problem/18869

18869번: 멀티버스 Ⅱ

풀이 전 나의 생각

M개의 우주가 주어지고 각 우주는 1부터 N까지 번호가 매겨진 행성 N개가 있다.

두 우주 A와 B에 있는 행성들이 아래의 조건을 만족한다면 균등한 우주라고 부른다.

 

조건

• Ai < Aj → Bi < Bj
• Ai = Aj → Bi = Bj
• Ai > Aj → Bi > Bj

우주, 행성, 행성의 크기의 범위

• 2 ≤ M ≤ 100
• 3 ≤ N ≤ 10,000
• 1 ≤ 행성의 크기 ≤ 1,000,000

그럼 이 조건들을 보고 바로 떠오르는 해결법은

그냥 for문을 여러개 돌려서 대소관계를 비교한 후에 값을 출력해주는 방법일 것이다.

 

하지만 이런 형식으로 진행할 경우 생길 수 있는 문제점은 행성의 크기가 입력의 수에 비해

너무 커서 메모리가 초과되거나 낭비 된다는 것이다. 따라서 행성의 크기를 인덱스로 바꾸는

좌표 압축 방법을 사용해야한다.

 

예를 들어 arr = {4, 4, 2, 1, 1, 3, 3} 의 배열이 있다고 가정하자.

우선 좌표 압축을 하기 위해 배열을 오름차순으로 정렬하고 중복을 제거해준다.

-> {1, 2, 3, 4}

그럼 이 {1, 2, 3, 4} 배열을 기준으로 기존 arr배열에 인덱스를 부여해줄 것이다.

 

1 = index 0번째

2 = index 1번째

3 = index 2번째

4 = index 3번째

 

이를 기존 arr배열에 적용하면

{3, 3, 1, 0, 0, 2, 2} 즉, {1, 2, 3, 4} 배열을 기준으로 한 인덱스 값을 기존 배열에 치환해준 것이다.

 

현재 arr배열은 숫자가 그렇게 크지 않지만, 만약 숫자의 범위가 메모리를 초과하거나 낭비할 정도로 크다면

좌표 압축은 굉장한 메모리를 절약할 수 있는 방법이 된다.  ex) 10억, 10억, 9억... -> 1, 1, 0...

 

여기까지 좌표 압축을 왜 해야 하는지 설명했다.

 

그럼 이를 사용하여 어떻게 균등한 우주임을 판단할 수 있는지 확인해야한다.

 

균등한 우주의 조건을 보면 결국 두 우주의 행성들은 대소관계가 같아야 한다는 것을 볼 수있다.

이 말인 즉, 수의 범위와 관계없이 대소관계만 비교해주면 된다는 것이다.

 

예를 들어 우주 A의 행성 {1, 2, 4, 3} 과 우주 B의 행성 {5600, 8000, 9500, 8300 } 를 비교한다고 했을 때

수의 범위를 떠나서 대소 관계의 입장에서만 봤을 때 결국 같은 배열이라는 것이다.

 

따라서 좌표 압축을 하여 각 배열의 값에 인덱스를 부여하고 단순히 인덱스의 값만 비교를 해서 우주가 균등한지

아닌지 찾아낸다. -> 정렬을 하든 중복 제거를 하든 대소 관계로 인한 로직은 같으니 결국 같은 값이 나오게 된다.

 

압축 과정

- vector<int> comp_arr = v;

압축할 벡터를 받아와서 빈 벡터에 값을 복사해준다.

 

- sort(comp_arr.begin(), comp_arr.end());

올바른 중복제거와 이분 탐색을 하기 위하여 오름차순 정렬을 해준다.

 

- comp_arr.erase(unique(comp_arr.begin(), comp_arr.end()), comp_arr.end());

중복을 제거하기 위한 부분이다.

unique기능은 현재 복사한 배열의 시작과 끝을 재배열 하는데 중복되는 값은 우측으로 밀고

중복되지 않은 값은 좌측으로 넣어준다. 

 

예를 들어 1, 1, 2, 3, 3, 4, 5, 5, 5, 6 라는 배열이 있다고 하면 1, 2, 3, 4, 5, 6, 5, 5, 5, 6과 같이 재배열한다.

그리고 마지막으로 쓰레기 값(중복 값)의 시작점을 반환해준다.

이런 쓰레기 값이 생기는 이유는 unique는 배열을 resize해주지 않기 때문이다. (rearrange != resize)

따라서 배열을 resize해줄 수 있는 erase를 사용하여 중복된 부분을 제거해줘야한다.

-> erase(중복의 시작) - 배열의 끝 = 중복이 제거된 배열

 

- int idx = lower_bound(comp_arr.begin(), comp_arr.end(), v[i]) - comp_arr.begin();

마지막으로 받아온 원본 벡터 값(v[i])을 돌며 현재 v[i]값이 어느 위치에 있는지 lower_bound를 사용하여

반환해준다. 참고로 lower_bound는 이분 탐색을 구현한 방법이다.

 

여기서 주의해야할 점은 lower_bound로 인하여 반환되는 값은 반복자의 위치값이 아닌 그 위치의 반복자가 반환된다.

그래서 int 형의 idx로 넣으려고 하면 타입이 맞지 않아 오류가 나게 된다.

따라서 현재 시작이 되는 반복자를 빼줘 온전한 인덱스 값을 int형으로 반환해준다.

 

- v[i] = idx;

마지막으로 얻어낸 인덱스 값을 원본 배열의 값에 넣어주는 치환 과정을 거친다.

 

 

결론

좌표 압축을 하여 인덱스 값으로 치환해준 두 우주의 행성을 비교할 때

인덱스 값이 다르다면 균등한 우주의 행성이 아니고

인덱스 값이 모두 같다면 균등한 우주의 행성이다.

 

이유는? 두 행성의 대소 관계가 같다면 치환해준 인덱스도 결국 동일하기 때문이다.

 

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

vector<vector<int>> M(101, vector<int>(0));

void Compression(vector<int>& v)
{
	vector<int> comp_arr = v;
	sort(comp_arr.begin(), comp_arr.end());
	comp_arr.erase(unique(comp_arr.begin(), comp_arr.end()), comp_arr.end());
	
	for (int i = 0; i < v.size(); i++)
	{
		int idx = lower_bound(comp_arr.begin(), comp_arr.end(), v[i]) - comp_arr.begin();
		v[i] = idx;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int m, n, ans = 0;

	cin >> m >> n;

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int size;
			cin >> size;
			M[i].push_back(size);
		}
		Compression(M[i]);
	}
	
	for (int i = 0; i < m - 1; i++)
	{
		for (int j = i + 1; j < m; j++)
		{
			if (M[i].size() == M[j].size())
			{
				bool equal_chk = true;

				for (int k = 0; k < M[i].size(); k++)
				{
					if (M[i][k] != M[j][k])
					{
						equal_chk = false;
						break;
					}
				}

				if (equal_chk) ans++;
			}
		}
	}

	cout << ans;
}