[Python] 백준 1138: 한 줄로 서기

 

 문제 해석과 구현에 대한 몸풀기를 시작하기 위해 구현에 가까운 문제를 선정했다. 해석하는데 크게 오래걸리지 않았고 스택의 성질을 이용하여 풀 수 있었다.

문제

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

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

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

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

입력

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

출력

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

 

예제 입력 1

4
2 1 1 0

예제 출력 1

4 2 1 3

예제 입력 4

7
6 1 1 1 2 0 0

예제 출력 4

6 2 3 4 7 5 1

 

정답 코드

N = int(input())

people = list(map(int, input().split()))
people = [(height, i) for i, height in enumerate(people)]

result = []
tmp = []

while people:

    h, i = people.pop()
    h -= len(result)

    if h == 0:
        result.append(i + 1) 

    elif h < 0:
        for _ in range(abs(h)):
            tmp.append(result.pop())
        result.append(i + 1)
    
    else:
        for _ in range(abs(h)):
            result.append(tmp.pop())
        result.append(i + 1)

while tmp:
    result.append(tmp.pop())
           
print(*result)

 

 스택의 후입선출 성질을 이용하였다. 결과를 담을 스택과 현재 push되어야 할 후보의 상태에 따라 결과 스택에서 빼줄 공간을 만들기 위한 임시 스택 2가지로 구성하였다. 알고리즘은 다음과 같다.

 

 1. 가장 왼쪽(우리 기준 오른쪽)부터 차례대로 (나보다 큰 왼쪽사람의 수, 순서)를 꺼낸다.

 2. 결과 스택에는 이미 나보다 큰 사람들이 들어가 있기 때문에, 결과 스택의 저장된 수 만큼 나보다 큰 왼쪽사람의 수를 뺀다.

 3. 위 2의 결과를 h라고 한다. h가 0이면 현재 나보다 큰 사람이 내 왼쪽에 더 이상 없으므로 현재 위치에 들어갈 수 있다.

 4. h가 0보다 작으면, 나보다 더 큰 사람이 과한 상태이다. 그러므로 h의 절댓값 만큼의 사람을 임시스택으로 옮기고, 그 다음 현재 후보가 push된다.

 5. h가 0보다 크면, 나보다 더 큰 사람이 부족한 상태이다. 그러므로 h 만큼의 사람을 임시스택에서 꺼내 결과스택으로 옮기고, 그 다음 현재 후보가 push된다.

 5. 1~4의 과정을 모든 사람이 후보로 한 번 씩 올라갈 때까지 반복한다.

 6. 반복이 끝나면, 임시스택에 남아있던 모든 사람들을 결과 스택으로 옮겨준다.