[Sort] Boj1015: 수열 정렬

[Sort] Boj1015: 수열 정렬

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

문제

P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.

배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.

입력

첫째 줄에 배열 A의 크기 N이 주어진다. 둘째 줄에는 배열 A의 원소가 0번부터 차례대로 주어진다. N은 50보다 작거나 같은 자연수이고, 배열의 원소는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 비내림차순으로 만드는 수열 P를 출력한다.

입출력 예제

문제 이해

1. 입력에 주어진 값은 리스트 A이다.
2. 우리가 구해야 하는것은 P의 수열이고, B는 P를 구하는 과정으로 이해하면 쉽다.
3. B리스트는 A의 값이 정렬되어 있는것과 같다.
4. A[i] = B[P[i]] 가 P를 구하는 수식인데, 쉽게 풀이해보자면 i번째 A의 값은 "i번째 P의 값"번째 B와 같다. 즉 정렬된 리스트 B의 인덱스를 리스트 A에 값의 순서대로 동일하게 나열하면 P의 값이 된다.
5. 아래의 코드를 보면서 주석을 참고하면 이해가 더 쉬울 것 같다.

Code | Python

import sys
si = sys.stdin.readline
N = int(si())
A = list(map(int,si().split()))

sortList = [[] for _ in range(N)]
#입력 받은 리스트 A의 값과 그 인덱스를 함께 저장해준다.
for i in range(N):
    sortList[i].append(i)
    sortList[i].append(A[i])

#A의 값을 기준으로 정렬해준다.
sortList.sort(key = lambda x:x[1])

#정렬된 리스트에 다시 한번 현재 인덱스(P값)를 append 해준다.
for i in range(N):
    sortList[i].append(i)

#가장 처음 리스트 A의 인덱스 순서대로 정렬 후, 마지막에 구한 P값을 출력한다.
for x in sorted(sortList,key = lambda x:x[0]):
    print(x[2], end = ' ')

Screenshot | Output

더 나은 코드

import sys
si = sys.stdin.readline
n = int(si())
A = list(map(int, sys.stdin.readline().split()))
B = [(x, i) for i, x in enumerate(a)]
B.sort()
P = [0 for _ in range(n)]
for i in range(n):
    P[B[i][1]] = i
for i in range(n):
    print(P[i], ' ')