[백준알고리즘] 1138번: 한 줄로 서기 -Python

[백준알고리즘] 1138번: 한 줄로 서기 -Python

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

1138번: 한 줄로 서기

키가 1인 사람부터 차례대로 세워주었다.

주어진 입력에 따라서 자신보다 키가 큰 인원의 수만큼 왼쪽에 빈자리를 놔두고 자리를 잡으면 된다.

 

예를 들어 주어진 2 1 1 0 에 대해서는 1보다 키가 큰 사람이 왼쪽에 두 명이 있어야 하기 때문에 왼쪽에 빈자리를 두 개 두고 위치하면 된다.

0 0 1 0

위와 같이 배치가 될 것이다. 다음은 2인 사람을 배치한다고 한다면 2보다 왼쪽에 1자리만 놔두고 배치를 하면 된다.

0 2 1 0

위처럼 배치가 될 것이다. 3인 사람은 왼쪽에 한명이 자신보다 크기 때문에 한 자리를 놔두고 위치하면 되는데, 다른 자리들은 자리가 이미 있으므로 아래와 같이 배치된다.

0 2 1 3

 

이런식으로 구현해주면 된다. 알고리즘 분류를 보니 그리디 알고리즘이라고 한다.

n = int(input())
h = list(map(int, input().split()))
ans = [0] * n
for p in range(1, n+1):
    t = h[p-1]
    cnt = 0
    for i in range(n):
        if cnt == t and ans[i] == 0:
            ans[i] = p
            break
        elif ans[i] == 0:
            cnt += 1
print(*ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다