[백준 알고리즘: python 3] #1015 - 수열 정렬

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

 

오랜만에 글을 쓰네요... 대학원 생활에 블로깅까지 하기가 힘들다는 것을 9월 초에 알고 허겁지겁 앞에 있는 일을 치우다 11월이 되었습니다 ㅜㅜ.. 최근에는 알고리즘 대회에 놀러가보자 ! 해서 문제를 이어서 풀어보려고 하고 있습니다.

 

원래 다음 풀 문제가 1014번인데 며칠을 붙잡고 풀어도 해결이 안돼서 우선 접어두었습니다. 찾아본 핵심 테스트 케이스들을 다 돌려 정답이 맞았는데도 accept이 안돼서 어젠 하루종일 좌절하다가 처음으로 "패스하고 다음꺼 풀자... 언젠가 풀리겠지" 하면서 1015번으로 넘어오게 되었네요.

 

서론이 길었네요! 1015번 문제는 수열 정렬이라는 이름의 문제로 소개되어 있습니다. 문제를 읽으면서 문제 의도가 잘 파악되지 않아서 예제 입력과 출력을 B[P(i)] = A[i] 에 직접 대입해서 풀어봤습니다.

 

예제에는,

 

<input>

3

2 3 1

 

<output>

1 2 0

 

이렇게 나와 있는데요, input의 내용을 해석하면 A 수열의 크기(3)와 이 수열의 수들(A[0] = 2,  A[1] = 3,  A[2] = 1)을 입력을 받는다는 내용입니다. 문제는 P 수열(P[0] = 1, P[1] = 2, P[2] = 0)을 찾아야 한다는 것입니다. 우선 B[P[i]] = A[i] 이 식에 대입을 먼저 해보면,

 

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 수열을 나열하면 1 2 3이 됩니다. 문제에서는 B 수열은  A 수열의 비내림차순 수열이라고 소개되어 있습니다. 그런 것 같군요!

 

Hint!

즉, P 수열은 A 수열의 각 숫자가 몇번째로 작은지를 0부터 정리한 수열이라고 할 수 있습니다. 예를 들면, 3 7 2 1 5가 A 수열로 주어진다고 할 때, P 수열은 2 4 1 0 3이 되겠지요. 이 의미가 먼저 정리가 된다면 코딩으로 구현하는 것은 그렇게 어렵지 않은 문제였습니다. 구현을 할 때 고려해야할 포인트는 다음으로 정리될 수 있습니다.

 

1. 입력받은 A 수열에서 가장 작은 수부터 차례로 각 숫자가 몇번째로 작은 숫자인지 파악해야합니다. 그 후에, python 3의 내장함수인 list method인 index() 를 활용하는 것이 핵심입니다. 이 함수는 내가 원하는 값이 list의 어느 index에 속하는지 return 해주는 함수입니다.
2. 단순하게 생각하면 안되는 부분이 있는데, 입력 받은 A 수열에는 숫자 중복이 허용된다는 점 입니다. 즉, 1 3 2 1 과 같이 A 수열이 주어질 수 있고, 문제의 정의에 따라 같은 숫자가 등장할 경우 나중에 나온 숫자가 더 큰 P숫자로 정의 됩니다. 그러니 A가 저렇게 주어지면 P 수열은 0 3 2 1이 되어야 합니다. 1번 포인트만 고려를 한다면 코딩 스타일에 따라 0 3 2 0이나 0 2 1 0과 같은 상황이 나올 수 있고 이는 오답입니다.

저는 구현을 할 때, (1) 먼저 입력받은 A 수열과 이 수열을 sort한 수열의 list를 할당하고, 기존의 A 수열의 각 숫자를 sort한 A 수열에서의 index를 찾는 방향으로 했습니다. (2) 그리고 2번 포인트를 잡기 위해서 이미 순회한 sort된 A 수열의 숫자를 조건에 의해 입력받지 않는 숫자인 -1로 대체하여 같은 index로 탐색되지 않도록 하는 방법으로 보완하였습니다. 즉, 코드가 끝나면 sort된 A 수열 list는 [-1, -1, -1, ..., -1]이 됩니다.

 

개인적으로 이 문제는 풍부한 내장함수를 가지고 있는 python의 장점을 잘 보여주는 문제였다고 생각합니다. C나 C++같은 경우에 이런 method들을 기본적으로 제공하지 않기 때문에 구현이 상대적으로 어려워졌을 것 같아요.

 

구체적인 코드는 다음과 같습니다.

import sys
import math

A_size = int(sys.stdin.readline())
A = sys.stdin.readline().replace("\n", "").split(' ')
A = [int(i) for i in A]

# A를 오름차순으로 정렬하여 작은 숫자부터 순서대로 정리된 새로운 list를 할당 
sorted_A = [i for i in A]
sorted_A.sort()

P = []
# A의 각 숫자들에 대해 sorted_A에서의 index를 찾아 몇번째로 작은 숫자인지 P 수열에 새롭게 append함.
for i in A:
    P.append(sorted_A.index(i))
    # 이미 할당한 숫자는 sorted_A에서 -1로 대채해 재탐색되지 않도록 함.
    sorted_A[sorted_A.index(i)] = -1

results = [i for i in P]

for result in results:
    sys.stdout.write(str(result)+' ')