[알고리즘|파이썬] 백준 2012 등수 매기기

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

📌 문제 탐색하기

시간 제한: 2초
메모리 제한: 256 MB

 

✏️ 구해야 하는 정답

문제

자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다.

당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다.

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

조건

- 1 ≤ N ≤ 500,000

- 예상 등수는 500,000 이하의 자연수

 

출력

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

---

📌 풀이하기 

예제 1.

5
1
5
3
1
2

실제 등수 : {1, ... , N}

예상 등수 : {a, b, ..., z}

해당 문제에서 적용을 해보면 다음과 같다.

실제 등수 : {1, 2, 3, 4, 5}

예상 등수 : {1, 5, 3, 1, 2}

 

예상 등수를 정렬해서 다시 보면 비교점이 보인다.

실제 등수 : {1, 2, 3, 4, 5}

예상 등수 : {1, 1, 2, 3, 5}

 

실제 등수 리스트와 예상 등수 리스트를 비교하여 중복 되는 숫자가 존재하면 지우고, 남는 숫자들의 차이 절댓값을 구하여 합하면 정답이 된다.

이 문제에서는 |4 - 1| = 3으로 정답은 3이다.

 

---

📌 코드 설계하기

1. N과 N개의 예상 등수값을 받아 예상 등수 리스트를 만든다.

2. 예상 등수 리스트를 오름차순으로 정렬한다.

3. 1 ... N 의 실제 등수 리스트를 만든다.

4. 실제 등수 리스트를 돌면서 예상 등수 리스트에 있는 경우 예상 등수 리스트에서 삭제를 하고, 없는 경우에는 남은 등수 리스트에 담는다.

5. 남은 등수 리스트와 예상 등수 리스트 값들의 차이를 절댓값으로 구하여 더하고 출력한다.

 

---

📌 시도 회차 수정 사항

1회차: 시간 초과

n = int(input())
predict = list()
actual = [i for i in range(1, n+1)]
left = list()

for _ in range(n):
    predict.append(int(input()))

for i in range(n):
    num = actual[i]
    if num in predict:
        predict.remove(num)
    else:
        left.append(num)

answer = 0
for j in range(len(left)):
    answer += abs(left[j] - predict[j])

print(answer)

remove()는 O(N) 의 복잡도를 가진다.

for 문이 O(N)이므로, 전체 O(N^2)로 주어진 시간이 넘어선다.

---

📌 정답 코드

import sys

n = int(sys.stdin.readline())
predict = [int(sys.stdin.readline()) for _ in range(n)]

predict.sort()

answer = sum(abs(predict[i] - (i + 1)) for i in range(n))

print(answer)