[Algorithms] 결정&그리디 알고리즘-역수열(그리디 알고리즘)

 

• 저녁에 피곤한 상태에서 풀다가 안풀려서 다음날 아침에 풀었더니 금방 풀렸다. 피곤해도 쉽게쉽게 풀리게끔 계속 알고리즘 공부에 정진!! 
• 그리디 알고리즘은 현재 직면한 상태를 먼저 해결하자는 관점에서 풀면 해결점이 보이는 것 같다
• 핵심은 주어진 역수열이 오름 차순 수열의 역수열이라는 점, 앞에서부터 순차적으로 찾아나가면 된다는 점을 잘 알아야 한다는 것  

 

• 풀이1

import sys
 
# sys.stdin = open("input", "rt")
total_num = int(input())
cnt_ls = list(map(int, input().split()))
 
check_ls = [0]*total_num                    # 숫자가 배정됐는지 아닌지에 대한 check list 겸 수열 정렬 할 리스트
for i, cnt in enumerate(cnt_ls):            # 역수열 리스트 for문
    total = 0
    for idx, check in enumerate(check_ls):  # check 리스트 for문
        if check == 0:                      # 비어있으면
            total += 1                      # 큰 수가 들어올 수 있는 경우니 count해주고
            if total == cnt+1:              # 앞에 큰 수 모두 잘 들어오고 이제 숫자를 넣어 줄 차례
                check_ls[idx]=i+1           
 
for j in check_ls:
    print(j, end=" ")

• 풀이2

 

import sys
 
# sys.stdin = open("input", "rt")
n = int(input())
a = list(map(int, input().split()))
seq=[0]*n
 
for i in range(n):                    # 역수열 for문
    for j in range(n):                # seq 리스트 for문
        if seq[j]==0 and a[i]==0:     # 칸이 비어있고 큰 수 배치할 칸을 다 찾았으면
            seq[j]=i+1
            break
        elif seq[j]==0:               # 칸이 비어있으면
            a[i]-=1
for k in seq:
    print(k, end=" ")