Algorithm - 역수열로 원수열 찾기(그리디)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[역수열로 원수열 찾기]

 

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

 

*출력 설명

원래의 수열을 출력하시오.

 

 

---

 

 

풀이(Python)

답안(난이도↑)

import sys 
sys.stdin = open('AA/input_31.txt', 'rt')

n = int(input())
a = list(map(int, input().split()))

seq = [0] * n
for i in range(n):
    for j in range(n):
        if a[i] == 0 and seq[j] == 0:
            seq[j] = i + 1
            break
        elif seq[j] == 0:
            a[i] -= 1
for x in seq:
    print(x, end= ' ')

# 출력 : 4 8 6 2 5 1 3 7

 

input_31.txt(입력)

8
5 3 4 0 2 1 1 0

 

 

중요내용

1. 변수 seq는 1차원 리스트로 원수열을 만드는 리스트 자료형으로 사용된다.
2. seq[j]에 원수열을 채울 때에는 반드시 1부터 n까지 조건을 차례대로 따지면서 한 개씩 채워간다.
3. a[i]의 값은 i+1의 값이 seq[j]에 들어갈 때, 자신 앞에 필요로하는 0의 개수(즉, 자신보다 큰 수의 자리)를 의미한다.
4. 즉, a[0]의 값인 5의 의미는 seq[j]로 만들어지는 원수열에서 1보다 큰 숫자가 1 앞에 5개 존재한다는 의미이다.
5. 이러한 원리를 참고하여 a[0]가 0이 될 때까지 1씩 값이 줄어들면서 비로소 a[0]이 0이 되는 순간, seq[5] 자리에 1이 들어가는 것이다. (단, seq[5]이 0인 경우에만 1이 들어가고 만약 0이 아니면 seq[6]의 자리에 1이 들어감)