[백준][Python] 2012번: 등수 매기기

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

 

 

오랜만에 파이썬을 사용해서 문제를 풀어보기로 했다.

 

문제를 처음 봤을 때에는 이해가 바로 안될 수 있다.

 

예제를 보면서 확인해보자

 

1, 5, 3, 1, 2 가 입력으로 들어왔는데

이 입력은 자신의 예상 등수이다.

 

만약 리스트를 정렬해 [5, 3, 2, 1,  1]로 해놓았다면

각각의 불만도는 [ 4 (5-1), 1 (3 - 2), 1 (2 - 3), 3 (1 - 4), 4 (1 - 5) ]가 된다.

 

즉, 최대한 인덱스+1과 입력받은 수가 가까워야 한다.

 

그냥 최대한 가까이 놓으면 되니까 정렬하면 끝난다.

 

오름차순으로 정렬할 경우 1에 가까울 수록 왼쪽에, N에 가까울 수록 오른쪽에 배치되기 때문에

불만도(거리)가 최소화될 수 있기 때문이다.

 

 

파이썬을 오랜만에 다뤄봐서 작성했더니 시간초과가 발생해 잘못한줄 알았다.

 

그런데 sys.stdin.readline()으로 input()을 변경해주었더니 바로 해결되었다.

한줄에 입력 하나라 이부분에서 시간이 많이 걸린 것 같다.

 

코드 보기

import sys
N = int(sys.stdin.readline())
people = [int(sys.stdin.readline()) for _ in range(N)]

people.sort()
sum = 0

for i in range(1, N+1):
    sum += abs(i - people[i-1])

print(sum)