백준 18869 멀티버스2 c++ // 값을 idx로 바꿔라, 이분탐색이용, unique사용법

 

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

18869번: 멀티버스 Ⅱ

1. 의사코드

1. 숫자 -> 크기순 idx로 변환한다

ex : 10 20 30 -> 0 1 2

ex2: 1 2 3-> 0 1 2

2. 변환후 같은배열이면, 같은우주이다.

 

2. 구현

1. v에 arr복사, 고유값만 남기기

2. v를 이분탐색하며 arr을 arr(idx)로 교체하기

 

 

3. 전체코드

#include <bits/stdc++.h>

using namespace std;

int m, n,ret,arr[104][10004];

//1. 숫자 -> idx로 변환
void compress(int a[]) {
	vector<int> v(a, a + n); //a를 v로 복사, 고유값만있어도 됨
	sort(v.begin(), v.end());
	//1. unique는 정렬후 사용해아함
	//2. unique는 중복원소(쓰레기)는 뒤로보냄, 쓰레기값의 첫주소반환
	//3. erase(쓰레기첫주소, 쓰레기막주소)로 쓰레기 제거
	v.erase(unique(v.begin(), v.end()), v.end());
	
	//숫자를 idx로 바꾸기
	//ex ) a: 10 10 20 20 30
	// v: 10 20 30
	//a` : 0 0 1 1 2
	for (int i = 0; i < n; ++i) {
		a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
	}

}

int compare(int a[], int b[]) {
	for (int i = 0; i < n; ++i) {
		if (a[i] != b[i]) return 0;
	}
	return 1;
}
int main() {
	cin.tie(0);

	cin >> m >> n;

	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> arr[i][j];
		}
		compress(arr[i]);
	}

	for (int i = 0; i < m-1; ++i) {
		for (int j = i + 1; j < m; ++j) {
			if(compare(arr[i], arr[j])) ret++;
		}
	}
	cout << ret;

	return 0;
}