[백준][1015] 수열 정렬

• Problem Link : https://www.acmicpc.net/problem/1015

문제

• 배열 A를 다음과 같이 A[P[i]] = B[i]처럼 배열 P를 이용해 배열 B를 만들 수 있다.
• 배열 A를 배열 P를 이용해 비내림차순 B를 만드려고 할 때 P를 구하여라.
• P가 여러 개라면 사전순으로 앞서는 것을 출력한다.

입력

• 첫째 줄, 배열 A의 크기 N이 주어진다.
• 둘째 줄, 배열 A의 원소가 0번부터 주어진다.

출력

• 배열 P를 출력한다.

풀이

우리가 만들고자 싶어하는 수열은 P이고 우리에게는 A밖에 없다. 문제를 쉽게 풀기 위한 방법 중 하나는 B를 먼저 만드는 것이다. B는 단순히 비내림차순이므로 sort를 이용해 B를 만들어줄 수 있다.

그럼 A를 B로 만드는 배열 P는 어떻게 구할까?

• A[P[i]] = B[i] 를 이해하면 굉장히 쉽게 P를 구할 수 있다.
• 위 식을 설명하면 B[i]의 원소는 A의 P[i]위치에 있어야 한다.
• 따라서 A 배열에 B[i] 원소의 위치가 P[i] 값이라는 뜻이다.

따라서 배열 B를 만들고 해당 B의 0번째 원소부터 A의 어디에 위치해 있는지 인덱스를 구해오고 해당 인덱스를 P에 추가하기만 하면 해결할 수 있는 문제이다.

p = []
for i in range(len(b)):
    idx = b.index(a[i])
    p.append(str(idx))

이 때 중복된 수가 있기 때문에 A에서 위치를 찾은 수는 -1로 바꿔준다. 이 때 index의 특징과 해당 과정이 더해져 자연스럽게 사전순으로 앞서는 P를 구할 수 있다.

index 함수는 일치하는 원소들 중 가장 앞에 있는 원소의 index를 반환한다.

위와 같은 index 함수의 특성 덕분에 자연스럽게 B의 원소와 같은 원소를 가지는 A의 원소 인덱스들 중 가장 작은 값이 P에 추가되고 해당 수는 -1로 변경되어 다음 탐색 때 그 다음으로 작은 원소들이 순서대로 들어오게 된다.

코드

import sys

ipnut = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
b = sorted(a)

p = []
for i in range(len(b)):
    idx = b.index(a[i])
    p.append(str(idx))
    b[idx] = -1
print(" ".join(p))