역수열을 원래의 수열로 되돌리기(그리디)

역수열 5 3 4 0 2 1 1 0 이 주어진다.

 

첫(1) 번째 요소 5는 원래의 수열에서 1 앞에 1보다 큰 숫자가 5개 있다는 뜻이고 

(1보다큼)(1보다큼)(1보다큼)(1보다큼)(1보다큼)1(?)(?)

두(2) 번째 요소 3은 원래의 수열에서 2 앞에 2보다 큰 숫자가 3개 있다는 뜻이먀

(2보다큼)(2보다큼)(2보다큼)2(?)1(?)(?)

세(3) 번째 요소 4는 원래의 수열에서 3 앞에 3보다 큰 숫자가 4개 있다는 뜻이다

(3보다큼)(3보다큼)(3보다큼)2(3보다큼)13(?)

 

n = int(input())  # 배열 크기 입력
a = list(map(int, input().split()))  # 왼쪽에 있는 자신보다 큰 수의 개수 리스트
seq = [0] * n  # 최종적으로 정렬될 배열 (초기에는 모두 0)
for i in range(n):  # 1번부터 n번 사람까지 배치
    for j in range(n):  # seq 리스트에서 올바른 위치 찾기
        if a[i] == 0 and seq[j] == 0:  # 내 앞에 있어야 할 큰 수를 다 배치했으면
            seq[j] = i + 1  # 현재 숫자를 해당 위치에 배치
            break  # 자리 찾았으므로 루프 종료
        elif seq[j] == 0:  # 아직 내 자리는 아니지만 빈자리라면
            a[i] -= 1  # 왼쪽에 있어야 할 큰 수의 개수를 하나 줄임 (다른 큰 수가 자리 잡음)

 

if a[i]==0 and seq[j]==0

왼쪽에 있어야 할 큰 숫자 개수가 0이면 이제 나타나는 빈 자리는 내 자리라는 뜻으로 

현재 숫자(i+1)를 해당 위치에 배치한다.

 

seq[j]==0 (and a[i]!=0)

아직 배치되지 않은 빈 자리가 있는데

a[i]은 0이 아니다 -> 이 빈 자리는 내 자리가 아니고 나보다 큰 숫자에게 이 빈 자리를 줄거야

-> 빈 자리를 큰 숫자에게 주면서 남은 큰 숫자 개수 a[i]를 1 감소시킨다. 

---

a[i]-=1 하는 이유

• 내가 배치될 수 없는 빈 자리는 건너뛰어야 한다. 
• a[i]는 내 왼쪽에 있어야 하는 큰 숫자의 개수를 의미하고
• 왼쪽에서 빈 자리를 하나 볼 때마다 a[i]-=1 해서 왼쪽에 배치될 큰 숫자에게 공간을 양보했다고 생

if a[i]==0 and seq[j]==0에서 배치하는 이유

• a[i]==0 은 더 이상 왼쪽에 있어야 할 큰 숫자가 없음을 의미. 빈 자리가 나타나면 처음 a[i]의 값만큼 큰 숫자에게 자리를 다 양보한 것. 이제 양보 안해.
• seq[j]==0 빈 자리가 있다. 이제 내 자리다.