[Python] 1015번 수열 정렬

1015번: 수열 정렬 (acmicpc.net)

1015번: 수열 정렬

---

 

22/08/30

 

이 날은 피곤해서 한 문제밖에 못 풀었던 날이다.

 

그 문제는 1015번 수열 정렬. 이전에 한 번 잠깐 보고 무슨 말인지 몰라서 패스했던 문제였는데, 나중에 예제를 보니 무슨 말인지 알 것 같아서 바로 풀어보았다.

 

---

 

접근 방법:

 

주어진 원래 수열이 있다고 해보자.

 

이를 수열 1이라고 칭하자.

 

그리고 수열 1을 오름차순(비내림차순)으로 수열을 정렬했을 때, 그 정렬된 수열을 수열 2라고 하자.

 

우리가 구하고자 하는 건 수열 2의 원소별 인덱스를, 수열 1과 같이 정렬되지 않은 상태로 만들고 싶은 것이다.

 

그림으로 보여지면 다음과 같다.

문제 설명하는 그림

그래서 파이썬 내장 함수 중 인덱스를 매길 수 있는 enumerate함수를 활용하여 이를 구현하면 될 것 같다는 생각이 들었다.

 

수열 2처럼 정렬된 수열을 만들고, enumerate로 리스트의 인덱스가 표현되도록 구현했다.

 

이후 수열 2를 다시 수열 1처럼 다시 만드는 작업을 for문으로 구현했다.

 

수열 2를 계속 반복하여 돌면서 수열 1과 매칭 되는 원소가 있을 때, 그 인덱스를 출력하고 동시에 그에 해당하는 원소를 수열 2에서 제거하는 과정을 거쳤다.

 

---

이 구현방법을 구현한 python3 코드이다. 더보기를 누르면 확인할 수 있다.

# 1015번 수열 정렬
# 정렬
import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().rstrip().split()))
sorted_P = list(enumerate(sorted(arr)))
for ele in arr:
    for index, arr_ele in sorted_P:
        if ele == arr_ele:
            sorted_P.remove((index, arr_ele))
            print(index, end = ' ')
            break