2012 등수매기기

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

2012번: 등수 매기기

 

내 풀이(맞음)

import heapq

n = int(input())
ary = []
for i in range(n):
    x = int(input())
    ary.append(x)
count = 0
heapq.heapify(ary)
j = 1
for i in range(n):
    if(ary[0] == j):
        heapq.heappop(ary)
        j += 1
        continue
    else:
        count += abs(ary[0] - j)
        heapq.heappop(ary)
        j += 1
        
print(count)

리스트를 힙으로 전환하고 ary[0]으로 최소값을 항상 구한다. 만약 1 1 2 5 5가 입력되면 처음에 1이 나오고 제대로 자리에 있어서 괜찮다. 하지만 두번째 1은 2등 자리에 있어서 불만도가 1이 쌓인다. 이런식으로 문제를 풀었다. 힙을 쓰지 않았을땐 시간 초과가 나왔다. 그리고 PyPy3로 제출하니까 정답이었다.