10. 역수열 (그리디)

역수열(그리디)

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

 

▣ 출력설명
원래 수열을 출력합니다.

 

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

 

 

문제풀이

import sys
sys.stdin=open("input.txt", "r")
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=' ')

 

해설

a = [ 5 3 4 0 2 1 1 0 ]

a 리스트에 있는 숫자는 자신자신보다 앞에 있는 큰 숫자의 "갯수"를 의미한다.


a[0] =5 ===> 1보다 큰 숫자가 좌측으로 5개 있다.
a[1] =3===>  2보다 큰 숫자가 좌측으로 3개 있다. 


seq리스트에 있는 "0의 의미" :  자기 자신보다 큰 "숫자" 
seq리스트에서 "0의 갯수" = 자신자신보다 큰 숫자의 "갯수" 



if(a[i]==0 and seq[j]==0):  

         a[i]==0 : 나보다 큰 애들(갯수) 앞에서 다 카운팅했어. seq[j]가  0으로 된 빈방 있니??  
         




elif seq[j]==0: 
      a[i]-=1

seq리스트에서 seq[j]==0의 의미 : seq[j]에 0이 존재해? = 나보다 큰 숫자 있어??

seq[j] ==0 이 참이라면 "나보다 큰 숫자가 존재한다"는 의미이므로

a[i]는 자기자신보다 큰 숫자의 "갯수"에서 -1로 줄여나가면, 
자기 자신 보다 큰 숫자 존재를 counting할 수 있다.  


최종적으로는 앞쪽에 있는 자기자신보다 큰 수 즉 "0"을 전부 카운팅하게 된다. 

 

 

※보충설명

1. cnt =3

    for _ in range(2):

       cnt +=1

 

    cnt = 5

    cnt가 3에서 5가 되었으므로 

    cnt가 2개 증가하였다는 사실을 알 수 있다. 

 

 

 

 

 

2.  cnt =5

     for _in range(5):

         cnt -=1

     

     cnt = 0

     cnt가 5 에서 cnt가 0이 되었으므로

     cnt가 5개 감소하였다는 사실을 알 수있다.

 

 

리펙토링

import sys
sys.stdin=open("input.txt", "r")
n=int(input())
a=list(map(int, input().split()))
seq=[0]*n


for i in range(n):
    for j in range(n):
        if seq[j]==0: 
            a[i]-=1
            if a[i] ==-1:
                seq[j]=i+1
                break

        

for x in seq:
    print(x, end=' ')

 

 

▶ -1인 지점에서 숫자를 대입한다.