[python] 백준 18869 멀티버스 Ⅱ

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

18869번: 멀티버스 Ⅱ

 

 

문제 해결

• 각 우주안에서 몇 번째로 큰 수인지를 알 수 있다면 비교하기 쉬울 것이다.
• 각 우주의 행성을 리스트안에 넣은 것을 A라하고 각 행성의 크기 등수를 적은 리스트를 B라 하면 f:A→B 는 일대일 대응이므로 바꿔서 계산해도 문제 없다.
• defaultdict 딕셔너리를 이용해 B가 같은 것들의 우주의 개수를 value로 하여 균등한 우주의 쌍을 계산할 수 있다. ( S[B] = n이라면 $ n \choose 2 $로 균등한 우주쌍을 구할 수 있다.)

CODE

import sys
input = sys.stdin.readline
from collections import defaultdict
m, n = map(int, input().split())
S = defaultdict(int)
for _ in range(m):
    planet = list(map(int, input().split()))
    sortedplanet = sorted(list(set(planet))) # 일대일 대응 함수 공역 만들기
    ranked = {sortedplanet[i]: i for i in range(len(sortedplanet))}
    vector = tuple([ranked[i] for i in planet])
    S[vector] += 1


answer = 0
for i in S.values():
    answer += (i*(i-1))//2
print(answer)