[인프런] 역수열

---

문제설명

1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 역수열이라고 한다. 예를 들어, 다음과 같은 수열이 있다고 가정하자. [4, 8, 6, 2, 5, 1, 3, 7] 이 때, 1 앞에 놓여있으면서 1보다 큰 수는 4,8,6,2,5로 5개이고, 2 앞에 놓여있으면서 2보다 큰 수는 4,8,6 이렇게 3개, 3 앞에 놓여있으면서 3보다 큰 수는 4,8,6,5 총 4개이다. 따라서 [4, 8, 6, 2, 5, 1, 3, 7] 의 역수열은 [5, 3, 4, 0, 2, 1, 1, 0]이 된다. 

 

n과 1부터 n까지의 수를 사용하여 이루어진 수열의 역수열이 주어질 때, 원래의 수열을 출력하라.

입력조건

• 첫째 줄에 자연수 N(3 <= N <= 100)이 주어진다.
• 둘째 줄에는 역수열이 숫자 사이에 한 칸의 공백을 두고 주어진다.

출력조건

• 원래 수열을 출력한다.

사고과정

• 어려웠다.. 정렬을 어떻게 활용해야 하는 것에 대해서도 명확히 판단이 서지 못했다..
• 결국 풀이를 보았고 설명만 듣고 다시 도전해보았는데도 구현하기가 힘들었다..
• 정답 소스코드를 분석해보기로 했고 문제 풀이의 핵심 포인트는 다음과 같다.
  • 원소가 0으로 이루어져있는 동일한 n크기의 리스트 seq를 초기화 시킨다. 여기에다가는 원래 수열을 담는다.
  • 주어지는 역수열의 인덱스를 1~n까지의 원소값이라고 간주(정확히는 인덱스+1 이긴 하지만)하고 원소값 기준 오름차순으로 하나씩 탐색한다. 
  • 탐색 할 때, seq을 앞에서부터 하나씩 도는데, seq의 원소값이 0이면서 해당 인덱스의 역수열 값(개수)이 0이라면 그 때, seq의 인덱스 값에 원래수열의 원소값(인덱스)을 집어넣는다. 만약 seq의 원소값은 0이면서 해당 인덱스의 역수열 값(개수)이 0이 아니라면 해당 원소 값 앞에 나와야할 수가 아직 있다는 것이므로 인덱스의 역수열 값에서 1을 차감함으로써 개수를 하나씩 줄여나간다.
  • 이런 원리가 동작 가능한 이유는 원소값을 오름차순 기준으로 탐색하기 때문이다. 예를 들어, 현재 원소값이 2를 탐색하고 있다면, 앞으로 탐색할 원소값들은 모두 2보다 무조건 크기 때문이다.

풀이(스스로 못 푼 풀이)

n = int(input())
arr = list(map(int, input().split())) # 개수
seq = [0] * n
# i = 수열 원소
for i in range(n):
    for j in range(n):
        if arr[i] == 0 and seq[j] == 0:
            seq[j] = i+1
            break
        elif seq[j] == 0:
            arr[i] -= 1
for s in seq:
    print(s, end=' ')
print()