백준 문제 풀이 - 멀티버스 2 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

💡 문제 재정의

위 조건을 만족한는 균등한 우주의 쌍의 개수를 출력하라

✏️ 계획 수립

먼저 균등한 우주를 구하는 방법은 각 우주를 정렬한 후 기존의 인덱스의 순서가 같다면 균등한 우주라고 볼 수 있다. 예를 들어 [3, 2, 1]에서 3은 0번째 인덱스 2는 1번째 인덱스 1은 2번째 인덱스라고 볼 수 있다. 이를 정렬하면 [1, 2, 3]이 되고 이를 인덱스 배열로보면 [2, 1, 0]으로 볼 수 있다. 또다른 배열을 보자. [6, 5, 4]의 인덱스 배열은 [0, 1, 2]이고 이를 정렬하면 [4, 5, 6]의 인덱스 배열은 [2, 1, 0]이다. [3, 2, 1]과 [6, 5, 4]는 균등한 우주이고 이는 정렬된 인덱스 배열을 비교하면 알 수 있다. 이를 그대로 코드로 옮기면 문제를 해결할 수 있다.

💻 계획 수행

import sys

if __name__ == '__main__':
    M, N = map(int, input().split())
    universe_list = []

    for _ in range(M):
        u_input = dict((x, True) for x in map(int, sys.stdin.readline().split())).keys()
        universe = {i: u for i, u in enumerate(u_input)}
        universe = sorted(universe, key=universe.get)
        universe_list.append(tuple(universe))

    count = 0
    for i in range(len(universe_list)):
        for j in range(i + 1, len(universe_list)):
            if universe_list[i] == universe_list[j]:
                count += 1

    print(count)

🤔 회고

중복된 값에 대한 처리때문에 해결에 오래걸렸다. 위에서 dict((x, True) ...).keys()의 요법으로 중복된 값을 제거하면서 순서를 유지할 수 있었다.