백준#1417 국회의원 선거 in Python

 

1417번: 국회의원 선거

이 문제를 풀기 위한 자료구조로 우선순위 큐가 적합하다는 것을 깨닫는 순간 빠르게 풀리는 문제다. 필자는 그걸 깨닫지 못해 여러 시행착오와 반례 선정을 거쳐 꽤 오랜 시간이 걸렸다...

---

후보가 1명일 경우, 바로 0을 프린트하고 종료한다.

후보가 2명 이상일 경우, 0번 인덱스(1번 후보)의 값을 target 변수에 저장해 따로 떼어두었다.

└ 이 자체가 필수적인 의미를 갖지는 않지만, 메모리를 고려하지 않는 내 작은 코드에서는 이 라인을 없애는 순간 시간 초과였다.

리스트에서의 최대값이 target보다 크거나 같으면 직접 target은 1 더하고, 최대값은 1 빼는 작업을 반복했다. 이 때 counter도 올렸다.

└ 처음에는 while 문을 돌리면서 1번 인덱스부터 순서대로 도는 방식을 생각했었다. 정말 돌은 방식이었다. 예를 들어 [0, 1, 5]의 경우에, [1, 0, 5]로 해버리는 방법이었다... 그냥 최대값부터 찾아서 빼면 될 것을 나는 왜 그랬을까?

└ 이 부분을 생각하지 못한게 문제 푸는 시간을 늘린 핵심이었다. 구리가 안돌아간다..ㅠ

---

n = int(input())
pq, cnt = [], 0

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

if n == 1:
    cnt = 0
else:
    target = pq[0]
    del pq[0]
    
    while(1):
        maxindex = pq.index(max(pq))
        if target <= max(pq):
            target += 1
            pq[maxindex] -= 1
            cnt += 1
        else:
            break
print(cnt)