백준 1417 국회의원 선거 (Python3)

 

이 문제는 구현 유형 중에 하나인데, 풀이 방법은 여러가지가 있는 것 같다.

후보 수 N명이 주어지고, 각 후보자에 대한 지지하는 사람 수가 주어진다.

그 중 1번 후보자를 지지하는 사람 수가 가장 많아지도록 다른 후보자 지지자 수에서 한 번씩 빼와서 더할 때마다 카운트를 하여 최댓값을 만들 수 있는 카운트의 최솟값을 구하는 문제다.

 

-나의 풀이 방법:

import sys
input = sys.stdin.readline

n = int(input())    #후보자 수
people = []    #후보자를 지지하는 사람 수를 담을 리스트 
cnt = 0    #연산 횟수 
for _ in range(n):    #각 후보자를 지지하는 사람 수를 입력받아 people리스트에 넣는다. 
    people.append(int(input()))  

while True:
    if people[0] == max(people):    #1번 후보자(people[0]) 지지자 수가 가장 큰 수일때
        for i in range(1, len(people)):    #1번 후보자 외의 후보자 지지자 수를 비교하여 
            if people[i] == people[0]:     #1번 후보자 지지자 수와 동일한 후보자가 있을 때
                cnt += 1          #연산 한 번 수행 후 종료 
                break
        break
    else:                #1번 후보자 지지자 수가 가장 큰 수가 아닐 때
        people[people.index(max(people))] -= 1      #가장 많은 지지자 수를 1감소
        people[0] += 1           #1번 후보자 지지자 수 1증가
        cnt += 1      #연산 1회 증가 
        if max(people) == people[0]:      #1번 후보자 지지자 수가 가장 큰 수가 됬을 때 종료
            for i in range(1, len(people)):    #다른 후보자 지지자 수 중 같은 값이 있을 시
                if people[i] == people[0]:
                    cnt += 1            #연산 1회 증가 후 중료 
                    break
            break
print(cnt)                 #cnt연산값 출력

아직은 if문과 for문을 많이 쓰는 방법으로 구현하고 있다.....ㅎㅎ

이 방법이 시간 복잡도 면에서 좋지 않은 방법이라고 해서 다른 사람들 코드를 보며 계속 공부해야 할 것 같다.

내 생각에 파이썬으로 계속 알고리즘을 풀어본 결과, 내장 함수나 문법을 많이 알고 있을수록 더 효율적이고 시간을 절약할 수 있는 코드를 작성할 수 있는 것 같다. 결국엔 지식의 중요성.....?!!

이와 같이 생각한 이유는 밑에 다른 사람의 코드를 보면 이해할 수 있다. 

하지만 이렇게 손코딩으로 1부터 10까지 직접 풀어보며 원리를 이해해나가는 것도 지금 단계에서는 중요하다고 생각한다.

 

-다른 사람 풀이

import heapq

n = int(input())

hq = []
for i in range(n):
    votes = int(input())
    if i == 0:
        dasom_votes = votes
        continue

    heapq.heappush(hq, -votes)

bribe_count = 0
while hq:
    votes = -heapq.heappop(hq)
    if votes < dasom_votes:
        break

    dasom_votes += 1
    bribe_count += 1
    heapq.heappush(hq, -(votes - 1))

print(bribe_count)

이 분은 파이썬 표준 라이브러리 중 하나인 힙을 이용해서 구현해냈다. 정말 다른 분들 코드를 볼 수록 대단한 분들이 많은 것 같다...ㅎㅎ 나도 열심히 공부해서 나중엔 한 줄로 알고리즘을 풀 수 있는...날이 오길...ㅎㅎ?