728x90
반응형
https://www.acmicpc.net/problem/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
입력
첫째 줄에 우주의 개수 M과 각 우주에 있는 행성의 개수 N이 주어진다. 둘째 줄부터 M개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.
출력
첫째 줄에 균등한 우주의 쌍의 개수를 출력한다.
풀이
Code
import sys
input = sys.stdin.readline
# 1. 좌표 압축 함수 정의
def Coordinate_Compression(lst) :
# 1-1. 중복 제거된 리스트를 정렬
re_lst = sorted(list(set(lst.copy())))
# 1-2. 딕셔너리를 사용해 압축된 좌표 부여
dic = dict()
for i in range(len(re_lst)) : dic[re_lst[i]] = i+1
# 1-3. 압축된 좌표 기반 리스트 재생성
for i in range(n) : lst[i] = dic[lst[i]]
# 1-4. 결과 리턴
return lst
m, n = map(int, input().split())
# 2.
multibus = [[] for _ in range(m)]
for i in range(m) : multibus[i] = Coordinate_Compression(list(map(int, input().split()))) # 좌표 압축 함수 실행
# 3.
ans = 0
for i in range(m) :
for j in range(i+1, m) :
# 비교 후 카운팅
if multibus[i] == multibus[j] : ans += 1
# 4. 결과 출력
print(ans)
728x90
반응형
'Coding Test > Baekjoon' 카테고리의 다른 글
[Python/BOJ] 2206. 벽 부수고 이동하기 (0) | 2023.08.13 |
---|---|
[Python/BOJ] 12099. 점심메뉴 (0) | 2023.08.12 |
[Python/BOJ] 5639. 이진 검색 트리 (0) | 2023.08.11 |
[Python/BOJ] 17394. 핑거 스냅 (0) | 2023.08.11 |
[Python/BOJ] 10819. 차이를 최대로 (0) | 2023.08.11 |