알고리즘 문제풀이/Greedy

백준 1138번: 한 줄로 서기(greedy)

Aytekin 2022. 5. 10. 10:55

입력값만큼 키가 큰 사람을 앞에 두고 줄을 세우는 문제이다.

 

왼쪽부터 숫자 0의 개수를 기준으로 위치를 찾아 줄을 세우면 된다.

 

예를 들어 2,1,1,0 이면

[0,0,1,0] -> 0을 2개 지나친 이후 1 위치

[0,2,1,0] -> 0을 1개 지나친 이후 2 위치

[0,2,1,3] -> 0을 1개 지나친 이후 3 위치

[4,2,1,3] -> 0을 0개 지나친 이후 4 위치

# 1138번 : 한 줄로 서기

n = int(input())
li = list(map(int,input().split()))
ans = [ 0 for i in range(n)]

for i in range(n):
    cnt = 0
    for j in range(n):
        if cnt == li[i] and ans[j] == 0:
            ans[j] = i + 1
            break
        elif ans[j] == 0:
            cnt += 1

print(*ans)
728x90