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

문제

백준 - 18869번: 멀티버스 Ⅱ

분석

각 우주에서 행성들의 크기가 주어졌을 때, 균등한 우주의 쌍 개수를 구하는 문제이다.
아래 조건이 두 우주가 균등한 조건이다.

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

각 우주들을 모두 비교하면 N이 최대 10,000이기 때문에 시간초과가 될 것이다.
따라서 각 행성 간의 대소비교를 편하게 하기 위해 좌표 압축이라는 테크닉을 사용한다.

1. 처음에 인덱스와 행성크기를 함께 리스트에 넣는다.
2. 행성크기를 기준으로 정렬한다.
3. 행성크기 대신 현재 인덱스를 넣는다.
4. 기존 인덱스를 기준으로 다시 정렬한다.
   기존 인덱스 값만 빼고 보면 좌표 압축의 결과가 나온다.

그런데 3.에서 정렬된 값들을 봤을 때 앞서 비교한 값과 같다면 인덱스를 그전 것과 똑같이 해야한다.
예를 들어 A : [40, 10, 10], B : [30, 10, 20] 일 때,
A : 40 > 10 = 10 이고 B : 30 > 10 < 20 이여서 두 우주는 균등하지 않지만,
A에서 좌표압축할 때 1.[[40, 0], [10, 1], [10, 2]] -> 2.[[10, 1], [10, 2], [40, 0]] -> 3.[[0, 1], [1, 2], [2, 0]] -> 4.[[2, 0], [0, 1], [1, 2]]가 되면 B와 같아진다.
따라서 3.에서 앞에서 비교한 값과 같다면 인덱스를 올리지 말고 같게 해야한다. 3.[[0, 1], [0, 2], [2, 0]]

이렇게 나온 압축좌표를 join함수로 합치고 그것을 키로 딕셔너리에 개수를 저장한다.
개수에 따라 nC2를 적용하면 균등한 우주 쌍을 구할 수 있다.
nCr은 math.comb()를 이용하면 쉽게 구할 수 있다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

import math
m, n = map(int, input().split())
def compress(lst):
    tmp = []
    for i, size in enumerate(lst):
        tmp.append([size, i])
    tmp.sort()
    pre = -1
    for idx, [size, _] in enumerate(tmp):
        if pre == size:
            tmp[idx][0] = tmp[idx-1][0]
        else:
            tmp[idx][0] = idx
        pre = size
    tmp.sort(key=lambda x:x[1])
    result = []
    for i, _ in tmp:
        result.append(i)
    return result

spaces = {}
for _ in range(m):
    lst = compress(list(map(int, input().split())))
    key = ''.join(map(str, lst))
    if key in spaces:
        spaces[key] += 1
    else:
        spaces[key] = 1

cnt = 0
for val in spaces.values():
    cnt += math.comb(val, 2)
print(cnt)

끝으로..

좌표 압축에 대해 배울 수 있었다.