백준 18869 [멀티버스 II] 파이썬

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

 

#백준 18869 멀티버스 II
import sys
from bisect import bisect_left
M,N=map(int,sys.stdin.readline().split())
univs=[]
indexes=[[] for _ in range(M)]
for i in range(M):
    univ=list(map(int,sys.stdin.readline().split()))
    univs.append(univ)  
    for v in univ:
        idx=bisect_left(univ,v)
        indexes[i].append(idx)
ans=0
for i in range(M):
    for j in range(i+1,M):
        if indexes[i]==indexes[j]:
            ans+=1

# print(indexes)
print(ans)

결국 이 문제의 핵심은 우주별로 행성들의 크기 서열이 같은지를 파악하는 문제였다.

 

이를 위해 이분 탐색을 이용해서 그 순서를 파악한다. (정렬되지 않았으므로, 정확한 순서는 아님. 잘못된 순서대로 순서가 작성됨)

(잘못된 순서도 상대적인 순서로 볼 수 있으므로 정답은 맞음)

 

딕셔너리를 이용해서 더 깔끔하게 푸신분의 코드를 첨부한다.

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

# m: 우주의 수 (각 우주는 행성 정보를 가짐)
# n: 각 우주에 있는 행성의 수
m, n = map(int, input().split())

# 같은 구성(정렬된 순위 기준)을 갖는 우주의 벡터를 key로, 개수를 세는 딕셔너리
universe = defaultdict(int)

for _ in range(m):
    # 한 우주의 행성 정보를 입력받음
    planets = list(map(int, input().split()))
    
    # 행성 정보를 정렬 후 중복 제거 (행성의 고유 크기 값들 정렬)
    sortedPlanets = sorted(list(set(planets)))
    
    # 행성 크기에 따라 정렬된 순위(rank) 매기기 (작은 값일수록 낮은 순위)
    rank = {sortedPlanets[i] : i for i in range(len(sortedPlanets))}
    
    # 원래 행성 배열을 rank에 따라 변환한 튜플 생성
    # 즉, 행성의 상대적인 크기 순서 벡터 생성
    vector = tuple([rank[i] for i in planets])
    
    # 해당 순서 벡터의 출현 횟수 증가
    universe[vector] += 1

# 같은 순서 벡터를 가진 우주 쌍의 수 계산
total = 0
for count in universe.values():
    # 같은 벡터를 가진 우주들 중 2개를 선택하는 경우의 수: 조합 count C 2
    total += (count * (count - 1)) // 2

# 결과 출력
print(total)