CS/Data Structure & Algorithm
역수열 (그리디 알고리즘)
Coding Kitsune
2022. 6. 10. 22:18
원래 수열을 [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=" ")
아이디어만 알고있으면 간단히 풀리는 문제다.