국회의원 선거

1417번: 국회의원 선거

 

나의 풀이

import sys
import heapq

def _gugu(n):
    answer = 0
    if (n == 1):
        return 0
    win_person, hq = int(sys.stdin.readline()), []
    for _ in range(n-1):
        heapq.heappush(hq, -1*int(sys.stdin.readline()))
    while True:
        if (win_person > abs(hq[0])):
            break
        answer += 1
        win_person += 1
        heapq.heappush(hq, heapq.heappop(hq)+1)
    return answer

n = int(sys.stdin.readline())
print(_gugu(n))

 

시간 복잡도

while True : 조건 만족시 까지 순회 ( 선형 시간 복잡도 )
        heapq.heappush(hq, heapq.heappop(hq)+1) : ( heapq 자료구조 로그 시간 복잡도 )
해당 알고리즘 시간 복잡도 :  선형 로그 시간 복잡도 ( O(n log n) )