[백준/1138] 한 줄로 서기 (Python)

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

1138번: 한 줄로 서기

Difficulty : Silver 2

Status : Solved

Time : 00:08:21

 

---

 

 

문제 설명

 

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

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

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

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

 

 

입력 및 출력

 

입력

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

 

출력

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

 

입력 예시

4
2 1 1 0

 

출력 예시

4 2 1 3

 

---

 

 

풀이

 

첫 번째 사람부터 생각해 보자. 첫 번째 사람(=키가 1인 사람)은 모든 사람이 자기보다 크므로, 왼쪽에 있는 모든 사람들 역시 자기보다 큰 사람이 된다. 즉 첫 번째 수는 첫 번째 사람의 index를 의미한다.

두 번째 사람의 경우, 두 번째 사람의 왼쪽에 있는 사람들은 1이 포함되어 있는 경우와 그렇지 않은 경우로 나눌 수 있을 것이다. 1이 포함되는 경우 1은 두번째 사람보다 작으므로 두 번째 사람의 index는 (두 번째 수) + 1이 된다. 1이 포함되지 않는 경우 첫 번째 사람의 경우와 같이 index는 (두 번째 수) 그 자채가 된다.

 

이를 확장해 보자. n번째 사람 왼쪽에 키가 큰 사람이 num만큼 존재한다면, 이 num은 "n-1명의 사람을 배치한 후, 비어있는 칸을 기준으로 세었을 때의 index"를 의미하게 된다. n-1번째까지의 사람들은 n번째 사람보다 작으므로 자기보다 키 큰 사람의 수에 영향을 미치지 않기 때문이다. 또한 이 n-1번째까지의 사람들이 이미 점유하고 있는 순서를 고려해야 하므로, 비어있는 칸을 기준으로 num만큼을 세면 n번째 사람의 index가 도출된다.

 

풀이 코드

N = int(input())
lst = list(map(int, input().split()))
answer = [0]*N

def find_empty(n) :
  cnt, idx = 0, 0
  while cnt <= n :
    if answer[idx] == 0 :
      cnt += 1
    idx += 1
  return idx - 1

for idx, left_num in enumerate(lst) :
  _idx = find_empty(left_num)
  answer[_idx] = idx + 1

print(*answer)

 

풀이 완료!