[백준] 멀티버스 Ⅰ : 20291번 - Python

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

18868번: 멀티버스 Ⅰ

 

 

 

문제를 풀면서 몰랐던 개념

 

(1) [Python] 리스트 원소들을 크기 순서대로 번호 매기기

arr = [10, 5, 1, 7] # 다음과 같은 리스트가 있음

s_arr = sorted(arr) # 순서를 찾기 위해 정렬

a_idx = []  # 순서 번호를 저장하기 위한 빈 리스트 선언

for i in arr:   # 위에서 선언한 리스트에 s_arr에서 찾은 순서(index)를 추가하기
    a_idx.append(s_arr.index(i)+1)  # 리스트 인덱스 번호는 0부터 시작하기 때문에 1을 더해주기

print(a_idx)


>>> [4, 2, 1, 3]

 

(2) 리스트의 각 요소들을 하나하나 비교해보기

-> 중첩 반복문 사용

temp = [1,2,3,2,1]	# 리스트 temp

count = 0

for i in range(len(temp)):	# temp의 길이만큼 비교를 반복해서 진행
    for j in range(i+1 , len(temp)):	# i번째원소를 그 다음 원소들이랑 비교하는 것이므로 초기값을 i+1로 설정
        if temp[i] == temp[j]:	# i번째 요소와 j번째 요소 비교(j는 계속 증가하면서 비교)
            count += 1	# 같은 값이 있다면 숫자 세주기

print(count)


>>> 2

 

 

 

문제의 접근 방법

 

행성의 크기들이 나열된 순서가 같다면 균등한 우주의 쌍을 판별하는 조건에 부합함. (규칙 찾기)

ex) 1 3 2 와 12 50 31이 있을 때,

이들이 나열된 순서는 가장 작은 수가 1번, 가장 큰 수가 2번, 중간 수가 3번째 순서로 나열돼있으므로 조건 성립!

 

 

 

내가 막혔던 부분

 

처음에 규칙을 찾아내는데 시간이 오래걸림.

 

 

 

문제 풀이 방법

 

(1) 우주의 개수(m)와 우주에 있는 행성의 개수(n) 입력받기

(2) m번만큼 반복문을 돌려 행성의 크기들을 n개 입력받아 리스트에 저장하기

(3) 각 행성들이 나열된 순서를 파악하기 위해 pset이라는 새로운 배열에 오름차순으로 정렬된 값을 저장하기

(4) 리스트 p_ind를 하나 더 선언해서 리스트 pset안에 있는 원소들을 순서대로 번호를 매겨 이 값들을 p_ind에 저장하기

(5) m번 저장되었던 p_ind 리스트들을 맨 처음에 선언해두었던 빈 리스트 temp에 저장하기

(6) temp안에 있는 원소들(각 우주에 있는 행성들의 크기가 저장되어있는 순서)을 하나씩 비교해서 같은 값이 있는지 판별하기

(7) 그 개수를 누적해서 count에 저장한 후 출력하기

 

 

 

소스코드

m,n = map(int, input().split())

temp = []

for i in range(m):
    s = list(map(int, input().split()))
    pset = sorted(s)
    p_ind = []
    for j in s:
        p_ind.append(pset.index(j)+1)
    temp.append(p_ind)

count = 0

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

print(count)