[알고리즘] 백준 1138번 한 줄로 서기 - 수학적 사고력

Created

2022/08/08

Tags

Algorithm

Python

2022-08-08 @이영훈

1138번: 한 줄로 서기

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다. 어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다. 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다.

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

접근방법

자리의 순서를 모두 0으로 초기화합니다 (orders)

입력의 두 번째 줄에 나오는 수는 자리의 순서(orders)의 0의 개수만큼 세알려서 띄우는 수입니다 (offsets)

자리 순서(orders)에서 0의 개수만큼 세아리고, 해당 자리가 0으로 비어있으면 수를 넣습니다

만약 0의 개수만큼 세아렸는데, 해당 자리가 다른 숫자로 기입되어 있으면 (0이 아니면) 그 다음 자리에 넣습니다.

파이썬 코드

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

orders = [0] * len(offsets)

for i in range(len(offsets)):
    zero_count = offsets[i]
    index = 0
		# 0의 개수만큼 세아리고, 해당 자리가 비어있는 지 확인
    while zero_count > 0 or orders[index] != 0:
        if orders[index] == 0:
            zero_count -= 1
        index += 1

    orders[index] = i + 1

print(" ".join(str(i) for i in orders))
Python
복사