💡문제접근
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 : 좌표압축
