역수열 (그리디 알고리즘)

 

원래 수열을 [0] * N 으로 초기화 시킨 뒤, 정렬이 되어있다 생각하고 1부터 경우를 생각하며,

 

원래 수열의 0을 역수열의 원소만큼 카운팅 하면 간단한 문제이다.

 

이중반복문을 돌리면서 i -> 역수열의 인덱스번호  j-> 원수열의 0을 카운팅하기 위한

 

인덱스 번호라 생각하고 cnt로 0을 카운팅하면서 어차피 오름차순으로 정렬되어 있기에,

 

앞에 더 작은 숫자가 나와있는건 신경쓰않고 오로지 0만 카운팅 해서,

 

cnt 와 역수열의 원소값이 같아지면 그때의 i+1 값을 원수열에 넣어주고 다음 반복문을 통해

 

다음값을 카운팅 해주면 된다.

 

import sys

#sys.stdin=open("input.txt", 'rt')

N = int(input())

rev = list(map(int, input().split()))

original = [0] * N

for i in range(N):

    cnt = 0

    for j in range(N):

        if original[j] == 0:

            if cnt == rev[i]:

                original[j] = i+1

                break

            cnt += 1

for num in original:

    print(num, end=" ")      

   

 

 아이디어만 알고있으면 간단히 풀리는 문제다.