백준 1138번: 한 줄로 서기 [실버 2] - Python

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

1138번: 한 줄로 서기

문제

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

출력

첫째 줄에 줄을 선 순서대로 키를 출력한다.

 

알고리즘 분류

구현

 

풀이

보통 구현 문제는 사람이 풀기는 쉽지만 코드로 구현하기는 어려운 문제들이 많은데, 이 문제는 마치 수수께끼 같아서 처음 봤을 땐 '와 이건 어떻게 해야 되지?'라는 생각이 들었네요! 하지만 다음과 같은 아이디어를 떠올리면 쉽게 해결할 수 있습니다.

1. 입력받은 리스트의 0인덱스 값 자리에 키가 1인 사람을 세운다. 왜냐하면 키가 1인 사람은 다른 사람들 모두가 자신보다 크기 때문에, 왼쪽에 있는 자신보다 큰 사람의 수가 곧 왼쪽의 있는 사람의 수를 뜻하기 때문
2. 키가 1인 사람을 제외하고, 입력받은 리스트의 1 인덱스 값 자리에 키가 2인 사람을 세운다.
3. 키가 n인 사람까지 모두 세울 때까지 2를 반복한다.

 

2번에서 키가 1인 사람을 제외하는 이유는 키가 2인 사람은 키가 1인 사람을 제외한 모든 사람이 자신보다 크기 때문이죠. 그렇기 때문에 1이 서있는 위치가 어디이든간에 이를 무시하고 왼쪽에 있는 자신보다 큰 사람의 수를 세면 되는 것입니다.

n = int(input())
inputList = list(map(int, input().split()))

#서는 순서의 인덱스 리스트
seqIndex = [i for i in range(n)]

#서는 순서 리스트
seq = [0]*n

for i in range(n):
    seq[seqIndex[inputList[i]]] = i + 1
    seqIndex.remove(seqIndex[inputList[i]])

for i in seq:
    print(i, end=' ')

 

 

코드 설명

seqIndex는 키가 n인 사람이 seq안의 어느 인덱스에 들어가야 하는지의 정보를 담을 리스트입니다. 아래의 예제를 통해 이해해 봅시다.

 

예제 입력

5
0 0 0 0 0

예제 출력

1 2 3 4 5

inputList = [0, 0, 0, 0, 0] 이고, seqIndex와 seq는 다음과 같이 초기화되어 있습니다.

seqIndex = [0, 1, 2, 3, 4]
seq = [0, 0, 0, 0, 0]

 

1. inputList[0] = 0이 키가 1인 사람의 자리가 되죠. 그러니 seq[0]에 1을 넣습니다. 그리고 중요한 것이 키가 1인 사람의 자리가 정해졌으니 그다음 사람의 자리를 정할 때에는 키가 1인 사람을 제외해야 합니다. 그렇기 때문에 여기서 seqIndex에서 0을 제거해 주는 것입니다. 그럼 다음과 같이 변하겠네요.

seqIndex = [1, 2, 3, 4]
seq = [1, 0, 0, 0, 0]

 

2. inputList[1]을 보면 0인데, 여기서부터는 이 0이 seqIndex의 인덱스가 되어서 그 값이 가리키는 자리에 키가 2인 사람이 서야 합니다. 즉 다음을 수행해야 하는 것이죠.

seq[seqIndex[inputList[1]]] = 2

수행하면 다음과 같이 변합니다.

seqIndex = [2, 3, 4]
seq = [1, 2, 0, 0, 0]

이를 반복해 주면 됩니다. inputList의 값들이 seqIndex의 인덱스가 되고 또 seqIndex의 값들이 seq의 인덱스가 되어서 조금 헷갈리는군요..! ㅎㅎ