[python] 백준 1138번

문제링크 : www.acmicpc.net/problem/1138 

1138번: 한 줄로 서기

키가 1부터 n인 사람 순서대로 왼쪽에 키 큰 사람의 수를 입력받을 때, 조건에 만족하도록 줄을 세우는 문제다.
줄에 대한 리스트를 비어 있는 칸으로 생각해보자. 키가 작은 사람부터 줄을 세운다고 가정하였을 때 1인 사람은 왼쪽에 키 큰 사람 2명이 있어야 하므로 empty | empty | 1 | empty 에 위치시킬 수 있다.
2인 사람은 왼쪽에 키 큰 사람 1명이 있어야 하므로 empty | 2 | 1 | empty 에 위치시킬 수 있다.
이런식으로, 키가 더 큰 사람의 수는 비어있는 칸을 지나친 수와 같으며, 키를 오름차순으로 줄을 세우기 때문에 누가 더 작은지, 같은지는 고려하지 않아도 된다. 그리디 유형이다.

# silver 2
import sys

sys.stdin = open("input.txt","r")
input = sys.stdin.readline

n = int(input())
arr = [0] + list(map(int, input().split()))
line = [0]*(n+1)

for i in range(1,n+1):
    left = 0 # 왼쪽에 있어야하는 키 큰 사람 수
    for j in range(1, n+1): # line를 순회
        if left==arr[i] and line[j] == 0:
            line[j] = i 
            break
        elif line[j] == 0:
            left+=1
for i in range(1,n+1):
    print(line[i],end = ' ')