BOJ 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를 출력한다.

예제 입력

3
2 3 1

예제 출력

1 2 0

풀이

비내림차순으로 만드는 수열이란..?

문제를 이해하는 것이 조금 어려운 문제였다.
용어를 설명하는 것 보다 예제를 통해서 이해하는 것이 더 빠를 것이다.
예제로 주어진 N = 3, A = [2, 3, 1]로 일단 설명해 보겠다.

기본적으로 주어진 리스트의 현재 값과 인덱스는 위와 같다.
이 리스트를 값을 기준으로 정렬하게되면 다음과 같다.

다음과 같이 인덱스 변화가 있을 것이다.
이것을 다시 원본의 순서와 같이 되돌린 후의 정렬 후 인덱스의 순서가
비내림차순이 되는 수열인 정답이 되게 된다.

해당 표에서 After Index의 순서인 [1, 2, 0]이 비내림차순으로 만드는 수열인 P다.

접근 방법

1. 리스트를 정렬해보자.

   • 원본 리스트가 손상되지 않게 해결해보자.

2. Dict Type을 사용해보자.

   • 키가 중복되는 경우는?
   • Stack을 활용해보자.

리스트를 정렬해보자.

원본 리스트를 정렬한 후 새로운 인덱스를 저장한 다음에
다시 원본 리스트를 사용해야하기 때문에 원본 리스트를
바꾸지 않고 원하는 값만 얻어낸 후에 리스트를 재사용할 수 있도록 한다.

for i, a in enumerate(sorted(A)):

다음과 같은 loop를 사용하면 된다.
sorted매서드를 사용해 원본 리스트를 따로 저장하지 않고도
정렬된 리스트를 접근할 수 있게되었다.
또한 enumerate매서드를 사용해 정렬된 리스트의 인덱스를 저장했다.

Dict Type을 사용해보자.

문제 풀이의 핵심이 되는 부분이다.

result = {}

다음과 같이 결과를 저장할 Dict타입의 변수를 하나 선언해주었다.
하지만, 지금 상황에서는 Dict타입을 사용해도 되는 것인가? 하는 의문을
가질 수 있다. 당연하다..! 왜냐하면 Key값이 중복되는 경우는?
어떻게 처리할 건데? 하고 생각할 수 있다.
이곳에서 스택을 활용하면 된다! 리스트의 Value에는 list타입 또한
사용할 수 있기 때문에, 이미 값이 존재하는 경우 int타입의 값을 list타입으로
바꾸어 출력을 할 때에 가장 먼저 들어온 0번째 인덱스의 데이터를 삭제하며
스택의 성질인 FIFO(First In First Out)을 활용해 해결할 수 있다.
다음 코드가 데이터를 삽입하는 부분이다.

for i, a in enumerate(sorted(A)):
    if a in result:
        if type(result[a]) is int:
            result[a] = [result[a], i]

        else:
            result[a].append(i)

    else:
        result[a] = i

Dict안에 이미 값이 존재할 경우 해당 Key값에 해당하는 Value의 type이
int형 일 경우 처음 중복된 경우이기 때문에 원본 값을 0번째에 새로운 값을 1번째에
갖는 리스트를 생성해서 저장하게 되면 된다. 또한 중복되는 경우가 3개 이상될 경우
이미 리스트가 생성되어 있기 때문에 append매서드를 사용해 새로운 값을 삽입해주었다.
데이터를 출력하는 부분도 마찬가지다.

for a in A:
    if type(result[a]) is list:
        print(result[a].pop(0), end=' ')

    else:
        print(result[a], end=' ')

다음과 같이 해당 값의 type이 list타입인지 확인한 후 맞을 경우
list의 pop매서드를 활용해 가장 먼저 들어온 0번째 값을 삭제하고 출력하고
list타입이 아닐 경우 그냥 해당 Value값을 출력하면 된다.

코드 구현부

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
result = {}

for i, a in enumerate(sorted(A)):
    if a in result:
        if type(result[a]) is int:
            result[a] = [result[a], i]

        else:
            result[a].append(i)

    else:
        result[a] = i

for a in A:
    if type(result[a]) is list:
        print(result[a].pop(0), end=' ')

    else:
        print(result[a], end=' ')

결과

문제를 해결하는 것은 어렵지 않았다.
하지만 문제 자체를 이해하는 데 시간이 엄청 오래걸렸던 문제였다.
예제를 통하여 문제를 이해하는 것이 훨씬 편하고 좋을 것 같다.

✅ 코드는 [여기]에서 확인할 수 있다.