[백준] 2012 - 등수 매기기 (Python)

난이도-Silver3

 

문제

2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.

KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다.

자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다.

각 사람의 예상 등수가 주어졌을 때, 김 조교를 도와 이러한 불만도의 합을 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다.

출력

첫째 줄에 불만도의 합을 최소로 할 때, 그 불만도를 출력한다.

 

 

접근법

사람이 5명일 때 가장 높은 등수부터 나열하면 각각 1등, 2등, 3등, 4등, 5등이 될것이다.

 

우리는 불만도의 총 합을 최소로 해야하므로, 입력받은 등수를 정렬 한 후 그 사람이 원래 받았어야 할 등수에서 실제 등수를 빼준 값이 그 사람의 최소 불만도일 것이다.

 

 

풀이

import sys
N = int(input())

arr=[]

sum=0
for i in range(N):
    arr.append(int(sys.stdin.readline()))
arr.sort()


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

print(sum)

 

 

매우 간단한 문제였지만 자꾸 시간초과가 났다.

 

그래서 input함수대신 sys.stdin.readline을 써주었다.

 

input() 내장 함수는 parameter로 prompt message를 받을 수 있다. 따라서 입력받기 전 prompt message를 출력해야 한다. 물론 prompt message가 없는 경우도 있지만, 이 경우도 약간의 부하로 작용할 수 있다. 하지만, sys.stdin.readline()은 prompt message를 인수로 받지 않는다.

 

또한, input() 내장 함수는 입력받은 값의 개행 문자를 삭제시켜서 리턴한다. 즉 입력받은 문자열에 rstrip() 함수를 적용시켜서 리턴한다. 반면에 sys.stdin.readline()은 개행 문자를 포함한 값을 리턴한다. 이 때문에 조금 귀찮은 점이 있기도 하다.

 

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

15552번: 빠른 A+B

 

이 문제를 한번 풀어보길 바란다.