[알고리즘]역수열

문제

1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞 에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 역수열이라 한다.
예를 들어 다음과 같은 수열의 경우
4 8 6 2 5 1 3 7
1앞에 놓인 1보다 큰 수는 4,8,6,2,5 이렇게 5개이고,
2앞에 놓인 2보다 큰 수는 4,8,6 이렇게 3개
3앞에 놓인 3보다 큰 수는 4,8,6,5 이렇게 4개,...

따라서4 8 6 2 5 1 3 7의 역수열은 5 3 4 0 2 1 1 0이된다.
n과 1부터 n까지의 수를 사용하여 이루어진 수열의 역수열이 주어졌을 때, 원래의 수열을 출 력하는 프로그램을 작성하세요.

▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<100)이 주어지고, 두 번째 줄에는 역수열이 숫자 사이에 한
칸의 공백을 두고 주어진다.

▣ 출력설명
원래 수열을 출력합니다.

▣ 입력예제 1
8
1 5 3 4 0 2 1 1 0

▣ 출력예제
1 4 8 6 2 5 1 3 7

[내 코드]

n=int(input())
num=list(map(int,input().split()))
tmp=[]
res=[]
for i in range(n):
    tmp.append((i+1,num[i]))
tmp.sort(reverse=True)
for i in range(n):
    res.insert(tmp[i][1],tmp[i][0])
print(*res)

1. 주어진 입력값은 각 1부터 n까지의 자연수들의 자기 자신보다 큰 수가 앞에 몇개 있는지에 대한 값이다.
   즉, 입력예제1에서 1은 1보다 큰 수가 자기자신앞에 1개 존재,2는 2보다 큰 수가 자기자신앞에 5개 존재...
2. 입력값을 튜플의 형태로 [0]인덱스는 자연수 1부터 n까지,[1]인덱스는 입력값을 넣는다.
3. 튜플의 [0]을 기준으로 내림차순 정렬한다.
4. n이 가장 큰 자연수이므로 n의 자리부터 배치시키는데 이 때 튜플의 [1]값은 계속 업데이트되는 res리스트의 해당 자연수가 위치하는 인덱스값이다.

[해설코드]

n=int(input())
a=list(map(int,input().split()))
seq=[0]*n
for i in range(n):
	for j in range(n):
    	if a[i]==0 and seq[j]==0:
        	seq[j]=i+1
            break
     	elif seq[j]==0:
        	a[i]-=1
for x in seq:
	print(x,end=' ')