[그리디] 역수열

📌

# problem: https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8

 

 

📍 역수열

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 이 된다.

 

 

<input>

8

5 3 4 0 2 1 1 0

 

 

✔️ code

 

import sys
sys.stdin=open("input.txt", "r")

N=int(input())
arr=list(map(int, input().split())) #역수열
seq=[0]*N

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 x in seq:
    print(x, end=' ')

 

 

# solve:

[0, 0, 0 ... * N] 의 seq 배열이 주어지고,

arr 배열은 다음과 같이 생각해야 한다.

 

number: 1 2 3 4 5 6 7 8

  arr:       5 3 4 0 2 1 1 0

 

즉, 1 앞에 1보다 큰 숫자가 5개 있어야 하므로 1을 index 5에 두고

2는 index 3에 같은 원리로 두게 된다.

이때 3은 앞에 3보다 큰 숫자가 3개가 있어야 하는데,

 

seq:  0 0 0 2 0 1 0 0

 

현재 seq 배열이 위와 같으므로 index 4에 들어가면 원하는 출력이 발생하지 않는다.

(2로 인해 앞에 큰 숫자 4개가 존재하지 않기 때문에)

따라서 1 다음 위치에 들어가야 한다.

 

1~8까지 정렬된 배열로 비교를 수행하기 때문에 그리디 알고리즘이다.

arr[i]-=1로 seq에서 몇 칸을 밀어야 하는지 알 수 있고,

해당 칸이 0이 아니라면 한 칸 뒤로 밀게 된다. 이 과정을 반복하며 위 풀이를 만족하게 되는 것이다.

 

 

 

>>>

 

푸는 동안 정말 고생했던 알고리즘 .. 😂

어쨌거나 풀렸으니 이제는 바이바이 ! 는 언젠가 다시 보는 날이 오겠지만