[18869] 멀티버스 Ⅱ

😲 문제

출처
M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.

두 우주 A와 B가 있고, 우주 A에 있는 행성의 크기는 A1, A2, ..., AN, 우주 B에 있는 행성의 크기는 B1, B2, ..., BN라고 하자. 두 우주의 행성 크기가 모든 1 ≤ i, j ≤ N에 대해서 아래와 같은 조건을 만족한다면, 두 우주를 균등하다고 한다.

Ai < Aj → Bi < Bj
Ai = Aj → Bi = Bj
Ai > Aj → Bi > Bj

입력
2 3
1 3 2
12 50 31

출력
1

❗️ 문제 재정의

• 우주의 개수와 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인가?
• 균등함의 조건은 대소관계가 일치한다는 의미이다.

각 우주마다의 각각의 행성을 다시 0~(n-1) 사이의 값으로 만들어줘야 한다.
그렇게 되면 각 행성에 대한 인덱스값이 매핑이 되는데 이를 행성의 크기로 다시 정렬을 해줘야 한다.
그렇게 정렬된 리스트가 우주의 개수(m)개가 나올텐데 같은 항목을 가지는 리스트가 몇 개가 나오는지 count하는것이다.

주의할 점

• 쌍의 개수라고 함은 중복되지 않는 두 요소의 개수를 의미한다.
  a,b,c,d의 쌍의 개수는 (a,b) (a,c), (a,d), (b,c), (b,d), (c,d) 로 6개이다.
  같은 우주의 개수를 구하고 조합(Combination) 공식을 이용하면 된다.
  n * (n - 1) // 2
• 정렬을 통해 인덱스를 구한다면 같은 숫자에 대해서는 따로 처리를 해야한다.
  2 3 입력
  40 10 10 -> (1,2,0) 이 나오지 않도록 해야함. -> (1,1,0) or (2,2,0)
  30 10 20 -> (1,2,0)

✔ 계획 수립

1. 좌표 압축
   1. 순위 매기기
   2. 딕셔너리를 통해 각각의 인덱스로 매핑하기
   3. 행성 크기순서로 정렬하기
   4. 정렬된 값에서 인덱스만 따로 뽑아내기
2. 중복되지 않는 쌍을 찾아서 개수를 세기
   1. 같은 값을 가지는 배열 탐색
   2. 같은 배열의 개수를 세기
   3. 배열의 개수를 조합을 통해 쌍의 개수를 계산하기

• 주의점 :
  • 딕셔너리를 통해 접근해서 탐색속도 높이기

👨🏻‍💻 문제 풀이

import sys
input = sys.stdin.readline
m, n = map(int, input().split()) # 우주의 개수, 행성의 개수
universes = [list(map(int, input().split())) for _ in range(m)] # 각 우주의 행성
def compress_coordinates(universe): # 좌표 압축
    unique_sorted_values = sorted(set(universe)) # 중복 값 제거(정렬을 이용하기에, 같은 값이 다른 인덱스를 가지면 안된다.)
    # 인덱스와 밸류 매핑
    value_to_index = {value: index for index, value in enumerate(unique_sorted_values)} 
    return tuple(value_to_index[value] for value in universe) # 딕셔너리로 처리하기 위해 리스트말고 튜플로 반환

# 각 우주를 좌표 압축
compressed_universes = [compress_coordinates(universe) for universe in universes]
compressed_universes = sorted(compressed_universes)  # 이분 탐색을 위해 정렬

from bisect import bisect_left, bisect_right
uni_dict = {}
for cu in compressed_universes: # 압축좌표를 통해 이분탐색으로 count하기
    if cu not in uni_dict:
        left = bisect_left(compressed_universes, cu)
        right = bisect_right(compressed_universes, cu)
        count = right - left
        uni_dict[cu] = count
answer = 0
for count in uni_dict.values(): # 조합으로 쌍의 개수 구하기
    answer += count * (count - 1) // 2
print(answer)

😅 회고

꽤나 힘들었다. 시간 초과가 너무 많이 나거라 예외처리를 하는 것을 깜빡하여 반례를 탐색하는 시간도 가졌다.

• 중복값 처리 : 같은 값이 다른 인덱스를 가지면 안된다. 때문에 제거를 하였다.
• 쌍의 개수 세기 : bisect_left, bisect_right를 이용하여 count 하고 조합 공식을 이용하는 것이 핵심이였다.