[백준] 18869번 : 멀티버스 Ⅱ

문제

 

 

접근 방식

결국 문제에서 요구하는건 두 우주의 행성들의 대소관계가 같은지를 판단하는 것이기 때문에

이분 탐색으로 좌표 압축을 한 후에 좌표 압축 결과가 같은 배열 쌍이 존재할 때마다

카운트를 1씩 증가시켜주기만 하면 된다.

20 10 30
10 20 60
80 25 79
30 50 80
80 25 81

 

예를 들어 위와 같이 5개의 우주마다 3개의 행성이 있을 때

행성의 크기 순으로 표현하면 다음과 같다

1 0 2
0 1 2
2 0 1
0 1 2
1 0 2

 

가장 작은 수부터 0이라고 표현 했을 때

행성의 대소관계가 일치하면 같은 행성이라고 볼 수 있기 때문에

1 0 2로 같은 1번과 5번 행성이 균등하다 볼 수 있고

0 1 2로 같은 2번과 4번 행성도 균등하다.

 

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int m = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());

		int[] arr = new int[n], sorted;
		int[][] zips = new int[m][n];

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < n; j++) {
				arr[j] = Integer.parseInt(st.nextToken());
			}

			sorted = Arrays.stream(arr)
				.distinct()
				.sorted()
				.toArray();

			for (int j = 0; j < n; j++) {
				zips[i][j] = Arrays.binarySearch(sorted, arr[j]);
			}
		}

		int total = 0;

		for (int i = 0; i < m; i++) {
			for (int j = i + 1; j < m; j++) {
				if (Arrays.equals(zips[i], zips[j])) total++;
			}
		}

		System.out.println(total);
	}
}