[백준] 18869번 멀티버스Ⅱ

출처: [백준] 18869번 멀티버스Ⅱ

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초 (추가 시간 없음)	512 MB	292	85	64	46.715%

---

문제

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

---

입력

첫째 줄에 우주의 개수 M과 각 우주에 있는 행성의 개수 N이 주어진다. 둘째 줄부터 M개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.

---

출력

첫째 줄에 균등한 우주의 쌍의 개수를 출력한다.

---

제한

• 2 ≤ M ≤ 100
• 3 ≤ N ≤ 10,000
• 1 ≤ 행성의 크기 ≤ 1,000,000

---

예제 입력 1

2 3
1 3 2
12 50 31

예제 출력 1

1

• (A, B) = (1, 2)
  • A1 = 1 < A2 = 3 이고, B1 = 12 < B2 = 50
  • A1 = 1 < A3 = 2 이고, B1 = 12 < B3 = 31
  • A2 = 3 > A3 = 2 이고, B2 = 50 > B3 = 31
• 모든 1 ≤ i, j ≤ N에 대해서 만족한다.

---

예제 입력 2

2 3
1 3 2
12 50 10

예제 출력 2

0

• (A, B) = (1, 2)
  • A1 = 1 < A3 = 2 인데, B1 = 12 > B3 = 10이다.
• 모든 1 ≤ i, j ≤ N에 대해서 만족하지 않는다.

---

예제 입력 3

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

예제 출력 3

2

• 1번과 5번 우주, 2번과 4번 우주가 균등하다.

---

힌트

• -

---

출처

• 데이터를 추가한 사람: akaishuichi
• 문제를 만든 사람: baekjoon

---

알고리즘 분류

• 정렬
• 값 / 좌표 압축

---

시간 제한

• -

---

풀이

• -

---

소스코드

import sys

input = sys.stdin.readline

M, N = map(int, input().split())

space_list = [list(map(int, input().split())) for _ in range(M)]

new_space_list = [[] for _ in range(M)]
dictionary = {}
for i in range(M):
    new_list = sorted(list(set(space_list[i])))
    for j in range(len(new_list)):
        dictionary[new_list[j]] = j
    for x in (space_list[i]):
        new_space_list[i].append(dictionary[x])

new_space_list.sort()
cnt, ans = 1, 0
for i in range(1, M):
    if new_space_list[i] == new_space_list[i - 1]:
        cnt += 1
    else:
        ans += cnt * (cnt - 1) // 2
        cnt = 1

ans += cnt * (cnt - 1) // 2
print(ans)