[알고리즘/그리디] 2012번 : 등수 매기기 - python

링크 : https://www.acmicpc.net/problem/2012

2012번: 등수 매기기

 

---

• 문제
• 소요시간: 55분

---

• 설계하기(접근방법) 

1. 입력받기

등수를 입력받는다

 

2. 구현하기

먼저 현재 등수에 자리 배치가 가능한 사람은 모두 배치한다

 

그 후 작은 등수를 순서대로 앞에서부터

빈자리를 가득 채운다

 

3. 출력하기

빈자리에 강제로 앉은 사람의 불만도의 합을 출력한다

 

---

• 코드(출력)

import heapq

n = int(input())

maybe_rank = []
real_rank = [0 for _ in range(n)]

for i in range(n):
    rank = int(input())
    if rank > n:
        heapq.heappush(maybe_rank, rank)
    else:
        if real_rank[rank - 1] == 0:
            real_rank[rank - 1] = rank
        else:
            heapq.heappush(maybe_rank, rank)
mad = 0

i = 0
while i < n:
    if real_rank[i] == 0:
        a = heapq.heappop(maybe_rank)
        real_rank[i] = a
        mad += abs((i + 1) - a)
    i += 1
print(mad)

---

• 얻어갈 부분

1. 자신을 N등이상으로 예측하는 멍청이 때문에 디버깅에 오래걸렸다