[백준/알고리즘/python/java] 1015번 - 수열 정렬

이미지를 누르면 문제링크를 보실 수 있습니다.

이미지를 누르면 문제링크를 보실 수 있습니다.

맨 처음에, 솔직히 문제가 잘 이해가 가지 않았다.

일단 예제 입력을 그대로 문제에 적용해보면,

 

입력으로 주어진 배열 A의 원소 2 3 1 은 아래와 같이 표현할 수 있다.

B[P[0]] = A[0]->B[1] = 2

B[P[1]] = A[1]->B[2] = 3

B[P[2]] = A[2]->B[0] = 1

다시한번, 문제를 잘 읽어보면, 여기서 B배열은 A배열의 비내림차순 배열이라는 것을 알 수 있었다. 

우리는 A배열로부터 B배열을 만들었는데, 그럼 자연스럽게 P배열은 A배열의 원소 크기 순이라는 것을 알 수 있다.

여기서 만약, 동일한 크기의 원소라면, 앞서 있는 것을 먼저 출력하면 된다.

예를 들어 A 배열이 1 3 2 2 라고 하면 P배열은 0 3 1 2 순으로 출력 될 것이다.

 

작성한 코드는 아래와 같다.

import sys
import math
input = sys.stdin.readline

N = int(input())
number_list = list(map(int, input().split()))

p_list = []

sorted_number_list = sorted(number_list)

for i in number_list:
    for j in sorted_number_list:
        if (i == j):
            p_list.append(sorted_number_list.index(j))
            sorted_number_list[sorted_number_list.index(j)] = -1
            break
for k in p_list:
    print(k, end=" ")

 여기서, 맨 처음에 오류를 만났다. 계속 nontype이라고 오류를 뿜어대서 뭔 소리지 했다.

실수는 sort함수를 쓰는 곳에서 나왔었다.

내가 오름차순으로 정렬된 객체를 얻으려면,

sorted_number = number_list.sort()

이렇게 쓰면 안된다. 이것은 그냥 기존에 있는 number_list를 sort(정렬)할 뿐이다. sort() 함수의 리턴 값은 None이므로 정말 주의해야 한다.

 

내가 의도한 바로, 기존의 리스트도 살리고, 그 리스트를 정렬한 새로운 리스트를 쓰고 싶었다면, 

sorted_number_list = sorted(number_list)

이런 식으로, sorted()함수를 써야 한다. 이 때는 괄호 안에 정렬하고 싶은 리스트를 넣어줘야 한다.

list.sort() 와 sorted(list)의 차이를 잘 파악해야 한다.

 

이렇게, 정렬된 새로운 리스트를 만들어주고, 기존 리스트와 새로 정렬된 리스트를 for문을 통해 검색하면서, 만약 같은 값이 나왔다면, 새로운 리스트 내에서 그 값의 인덱스 값을 p_list에 추가해주고 새로 정렬된 리스트에서의 해당 원소는 -1 로 교체함으로써, 다시 검색되는 것을 방지해준다.