[G5] 백준 18869번 멀티버스 Ⅱ C++ 정렬, 브루트포스 알고리즘, 값/좌표 압축

리뷰

 

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

각 행성의 값들을 압축하여 인덱스화 하고, 브루트포스로 비교하여 쌍의 개수를 구하는 문제

 

 

전역 변수

• M : 우주의 최대 개수를 정의할 상수 변수
• N : 행성의 최대 개수를 정의할 상수 변수
• m : 우주의 개수를 저장할 변수
• n : 행성의 개수를 저장할 변수
• arr : 우주당 행성의 크기를 저장할 2차원 배열

 

함수

없음

 

 

문제풀이

1. m, n값을 입력 받고, m개의 행성을 순회하는 for문을 개행한다.
2. 정수형 벡터 cs를 초기화 하고, n개의 행성 크기를 입력 받아 arr배열과 cs벡터를 초기화한다.
3. sort함수를 통해 cs를 오름차순으로 정렬하고, erase, unique함수를 통해 중복을 제거한다.
4. 다시 n개의 행성을 순회하며 arr의 값을 압축된 인덱스로 변경한다.
5. 모든 입력과 값압축을 마친 후 변수 sum을 0으로 초기화한다.
6. 브루트포스 알고리즘을 통해 배열 값 구조가 동일한 행성들의 쌍의 개수를 구해 sum에 더해준다.
7. sum에 저장된 값을 출력한다.

 

트러블 슈팅

1. M이 최대 100, N이 최대 10000인데 이를 거꾸로 정의해주어 WA를 받았다.
2. 두 상수 변수의 값을 변경해 주어 AC를 받았다.

 

참고 사항

1. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다는 조건이 있으므로 브루트포스를 반쪽만 수행했다.
2. 탐색 중 인덱스가 동일하지 않은 배열을 만난 경우 도중에 break처리해 주면 된다.

 

정답 코드

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

const int M = 100;
const int N = 1e4;
int m, n;
int arr[M][N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> m >> n;
	
	for (int i = 0; i < m; ++i) {
		vector<int> cs;

		for (int j = 0; j < n; ++j) {
			cin >> arr[i][j];
			cs.push_back(arr[i][j]);
		}

		sort(cs.begin(), cs.end());
		cs.erase(unique(cs.begin(), cs.end()), cs.end());

		for (int j = 0; j < n; ++j) {
			arr[i][j] = lower_bound(cs.begin(), cs.end(), arr[i][j]) - cs.begin();
		}
	}

	int sum = 0;
	for (int i = 0; i < m - 1; ++i) {
		for (int j = i + 1; j < m; ++j) {
			bool flag = true;

			for (int k = 0; k < n; ++k) {
				if (arr[i][k] != arr[j][k]) {
					flag = false;
					break;
				}
			}

			if (flag) ++sum;
		}
	}
	cout << sum;
}