문제
https://www.acmicpc.net/problem/1015
풀이
- 수열
P:0부터N-1까지의 수를 한 번씩 포함하고 있는 수열 - 배열
A와 수열P가 주어졌을 때,B[P[i]] = A[i]로 정의된B가 비내림차순이 되도록P를 만들어서 출력
B[P[i]] = A[i]란 A[i]가 B의 P[i] 위치로 가야 합니다.
따라서 B는 A를 재배열한 배열입니다.
A의 값을 오름차순으로 정렬한 뒤, 그 값들이 어디 인덱스에 위치한지 확인하여 P를 구성하면 됩니다.
우선 A[i]와 인덱스를 튜플 형태로 저장합니다.
후에 이를 A[i]를 기준으로 정렬해줍니다.
arr = sorted((v, i) for i, v in enumerate(a))이렇게 되면 A[i]를 기준으로 정렬이 됩니다.
어떻게 됐는지 한 번 보면
B[0] = A[2] → P[2] = 0
B[1] = A[0] → P[0] = 1
B[2] = A[1] → P[1] = 2
B[3] = A[3] → P[3] = 3
위와 같은 형태로 정렬이 되어 있습니다.
이제 이 값들을 결과 배열 p에 저장을 해보겠습니다.
즉, A[i]가 정렬된 배열에서 idx번째 위치로 간다면 idx를 P[i]에 저장합니다.
p = [0 for _ in range(n)] # 값들을 저장할 배열
for idx, (v, i) in enumerate(arr): # 정렬된 위치 -> A의 원래 인덱스
p[i] = idx이렇게 하면 B[P[i]] = A[i] 관계가 성립됩니다.
B는 항상 정렬된 형태가 되므로 비내림차순이 성립됩니다.
코드
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
arr = sorted((v, i) for i, v in enumerate(a))
p = [0 for _ in range(n)]
for idx, (v, i) in enumerate(arr):
p[i] = idx
print(*p)