[코딩테스트 공부] 수열 정렬

출처 : https://www.acmicpc.net/problem/1015

풀기 전에 할 말

푸는데 있어서, 알고리즘이 어렵기 보다는, 문제 해석이 너무 어려워서 골머리를 앓은 문제입니다. 일단 제가 문제를 해석한 방식부터 소개를 해보고자 합니다.

나는 어떻게 생각을 했을까?

일단 악필 죄송합니다

일단 입력으로 받아오는 A라는 수열을 먼저 정렬을 하기로 했습니다. 정렬을 한 이후에는, A를 선형으로 탐색하여서 A에 있던 숫자들은 B의 어느 인덱스로 이동을 하였는지 에 관한 정보를 출력하는 것으로 해석했습니다.

그러기 위해서는 다음의 과정을 거쳐야합니다.

• A를 정렬한다
• A와 정렬된 수열을 비교하여서, 어느 인덱스로 이동을 하였는지를 특정 인덱스에 저장한다

일단 위의 설명만 들어보면, 첫번째 과정은 파이썬의 sort 함수를 사용할 예정이며, 두번째 과정은 따로 구현을 하여서 O(N^2)의 복잡도를 가지는 코드를 구현할 예정임을 알 수 있습니다!

일단 코드부터 보실까요?

import sys

input = sys.stdin.readline

N = int(input())
target_list = list(map(int, input().split()))
sorted_list = sorted(target_list)
result_list = []

for number in target_list:
    for i in range(0, N):
        if number == sorted_list[i] and i not in result_list:
            result_list.append(i)
            break

print(*result_list)

코드 해석해봅시다

for number in target_list:
    for i in range(0, N):
        if number == sorted_list[i] and i not in result_list:
            result_list.append(i)
            break

일단, target_list의 숫자를 하나씩 sorted_list와 비교를 하여서, sorted_list[i]와 number가 일치하면, 그 i를 result_list에 넣는 전략을 취하였습니다.

그런데 한 가지 예외 사항이 있는게, target_list의 숫자는 중복이 허용된다 이 말입니다!

따라서, i를 곧이 곧대로 result_list에 넣으면 오답입니다. 따라서 한 가지의 조건을 더 달아줘야 하는데, 그 부분이

i not in result_list

입니다. 이는, i가 기존에 result_list에 담겨있지 않은 경우에만 result_list에 담으라는 소리입니다.