[백준] 18869번 멀티버스Ⅱ

💡문제접근

• 2 ≤ M ≤ 100, 3 ≤ N ≤ 10,000, 1 ≤ 행성의 크기 ≤ 1,000,000의 범위를 보고 일단 이 문제는 2중 반복문으로 푸는 문제가 아니라는 것을 알고 좌표 압축을 이용한 문제 풀이 방법을 선택했다.

💡테스트케이스

입력
5 3
20 10 30
10 20 60
80 25 79
30 50 80
80 25 81

출력
2

• [20, 10, 30] : [1, 0, 2]
• [10, 20, 60] : [0, 1, 2]
• [80, 25, 79] : [2, 0, 1]
• [30, 50, 80] : [0, 1, 2]
• [80, 25, 81] : [1, 0, 2]

따라서, 1번 우주와 5번 우주, 2번 우주와 4번 우주가 균등하다는 것을 알 수 있다.
얼른 코드로 구현해봐야겠다.

💡코드(메모리 : 50688KB, 시간 : 708ms)

from collections import defaultdict
import sys
input = sys.stdin.readline

universe = defaultdict(int)
M, N = map(int, input().strip().split())
for _ in range(M):
    # 행성의 크기 입력값으로 받아옴
    planet = list(map(int, input().strip().split()))
    # 행성의 크기를 오름차순으로 정렬
    sorted_planet = sorted(planet)
    # 정렬된 행성의 크기를 순서대로 인덱싱
    sorted_ranks = {sorted_planet[i] : i for i in range(len(sorted_planet))}
    # 입력값 순서대로 다시 인덱싱을 해줘야 함
    ranks = tuple(sorted_ranks[i] for i in planet)
    universe[ranks] += 1

# 한 쌍 즉, 딕셔너리의 값이 2이상이면 nC2로 값을 가져오면 됨
result = 0
for val in universe.values():
    result += val * (val - 1) // 2
print(result)

💡소요시간 : 47m

연관 문항 : 백준 - 18870 : 좌표압축