18869 멀티버스 Ⅱ
M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.
두 우주 A와 B가 있고, 우주 A에 있는 행성의 크기는 A1, A2, ..., AN, 우주 B에 있는 행성의 크기는 B1, B2, ..., BN라고 하자. 두 우주의 행성 크기가 모든 1 ≤ i, j ≤ N에 대해서 아래와 같은 조건을 만족한다면, 두 우주를 균등하다고 한다.
첫째 줄에 우주의 개수 M과 각 우주에 있는 행성의 개수 N이 주어진다. 둘째 줄부터 M개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.
첫째 줄에 균등한 우주의 쌍의 개수를 출력한다.
시간 - 2초
메모리 - 512MB
import sys
input = sys.stdin.readline
from collections import defaultdict
m, n = map(int, input().split())
universe = defaultdict(int)
for _ in range(m):
# 행성 입력 받기
planets = list(map(int, input().split()))
# 행성 정렬 ( 구성 같은 행성 한개만 세기 )
sortedPlanets = sorted(list(set(planets)))
# 행성 순위 지정
rank = {sortedPlanets[i] : i for i in range(len(sortedPlanets))}
# 입력 받은 행성에 맞게 순위 저장
vector = tuple([rank[i] for i in planets])
# 해당 순위 벡터에 대한 개수 추가
universe[vector] += 1
sum = 0
for i in universe.values():
# n개 중 2개의 우주를 엮어야 하기 때문에 n C 2 를 해줘야 함 (중복 제외)
sum += (i * (i - 1)) // 2 # nC2
print(sum)
해당 문제를 일반 브루트포스로 풀게 되면 O(M^2 * N^2)의 시간복잡도가 발생하기 때문에
좌표 압축기법을 사용해야 한다.
해당 함수는 dict를 만들때 초기값을 선언해준다. defaultdict(int)로 할 경우 키에 대한 초기값을 0으로 선언해준다.
tuple을 통해 각 순위값이 저장이 되기 때문에 일일히 각 우주끼리 직접 비교할 필요가 없게 된다.