https://www.acmicpc.net/problem/1138
n = int(input())
arr = list(map(int, input().split()))
answer = [0 for _ in range(n)]
for i in range(n):
cnt = 0
for j in range(n):
if answer[j] == 0 and cnt == arr[i]:
answer[j] = i + 1
break
elif answer[j] == 0:
cnt += 1
print(' '.join(map(str, answer)))우선 이것이 어떻게 동작하는지 살펴보자.
말로 설정하자면 다음과 같다.
예를들어 2 1 1 0일때,
0번째 2는 자기보다 큰 사람이 왼쪽에 2명 있다는 뜻이다.
즉 왼쪽에서 두 칸 뛰고 인덱스 2번째에 들어간다.
1번째인 1은 자기보다 큰 사람이 1명 있다는 뜻이므로 한칸을 뛰고 인덱스 1번째에 들어가게된다.
| 2 | 1 | 1 | 0 |
이 있을 때, 첫번째 2를 보자.
| 2 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 |
이중 반복문을 통해 answer[j]를 보면 0이다. 그러나 arr[i](0번 인덱스, 숫자 2)는 cnt와 같지않다.
여기서 cnt는 왼쪽에서 몇 칸 떨어졌는지를 의미한다.
때문에 cnt += 1이 된다.
... cnt가 2일때, j는 2가 된다.
즉 왼쪽에서 2칸 떨어져있고 answer[2]는 현재 비어있다. 때문에 answer[j]에 숫자2, 즉 인덱스 0번째, 다시말하면 1번째 순서가 들어가게된다.
그럼 arr[2]인 1을 보자.
왼쪽에서 1만큼 떨어져있다.
그럼 answer[1]에 넣으면 되지 않나? 싶겠지만
i가 2인경우 answer배열은 다음과 같다.
| 0 | 2 | 1 | 0 |
즉 왼쪽에서 한칸 떨어진 answer[1]는 이미 자리가 차있다.
그럴경우를 대비해서 cnt는 answer[j]가 0일때만 +1이 된다.