[알고리즘] 역수열(그리디)

(문제) 역수열(그리디)

---

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)이 주어지고, 두 번째 줄에는 역수열이 숫자 사이에 한칸의 공백을 두고 주어진다.

출력설명

원래 수열을 출력합니다.

테스트케이스

입력예제	출력예제
8 5 3 4 0 2 1 1 0	4 8 6 2 5 1 3 7
10 4 8 4 0 5 2 3 0 0 0	4 8 9 6 1 3 10 7 5 2

---

해결방법

그리디이기 때문에 정렬을 해야한다는 사실을 가지고 정렬할 것을 찾아 보았지만…

전혀 문제를 해결하기 어려워서 결국 방법을 찾아봤다…

이미 문제 입력에 들어오는 것이 정렬되어서 들어오고 있는 것이기 때문에, 굳이 정렬할 필요가 없었다.

5 3 4 0 2 1 1 0 을 예로 들어보자.

5는 1보다 큰 수가 자신의 앞에 5개가 있다는 것이고, 3은 2보다 큰 수가 자신의 앞에 있다는 것이다.

마찬가지로 뒤에 있는 것 또한 숫자의 의미는 이런식으로 나타내고 있다.

자, 의미를 알았으니 문제를 해결해보자.

이 문제를 해결하기 위해서는 추가적인 리스트가 필요하다.

우리는 이 리스트 이름을 answer 라고 하자.

answer는 입력으로 들어오는 개수 만큼 0으로 전부 초기화 한다.

answer에 있는 각 0이 의미하는 것은 이 안에는 큰 값이 들어갈 수 있다! 라는 의미를 한다.

반복문을 이용하여 기존 리스트를 순회한다.
(순회 할 때는 index 또한 같이 표시한다)

반복문 시작에 count 라는 변수를 처음 0으로 초기화 하고, 기존 리스트 안에 있는 값과 count 가 동일하고 현재 answer 인덱스 위치에 값이 0일 경우 answer 인덱스 위치에 순회할 때 이용한 index 값 + 1을 넣는다.

이때 같으면 반복 순회를 break 한다.

그렇지 않을 경우 count 를 + 1 계속 시킨다.

이게 무슨 소리인지 잘 모를 수 있다.

한번 그림을 통해서 설명 해 보겠다.

아래의 그림과 같이 count는 처음 0으로 초기화 하고, 순회를 한다.

index = 0 인 경우

---

index = 1 인 경우

---

index = 2 인 경우

여기는 다른 것과 달리 answer 리스트 안에 값 중 0이 아닌 것이 있어서 count를 따로 하지 않고 그냥 넘어간다.

이런 식으로 answer 리스트를 채워 나간다.

---

코드

n = int(input())

arr = list(map(int, input().split()))

answer = [0] * n

for idx, val in enumerate(arr):
    count = 0
    for i in range(n):
        if answer[i] == 0 and count == val:
            answer[i] = idx + 1
            break
        elif answer[i] == 0:
            count = count + 1

print(*answer)