[백준-Python] 문제 1417 - 국회의원 선거

문제

 

1417번: 국회의원 선거

 

---

 

풀이

 

단순 구현

처음 문제를 이해하고 생각나는 대로 구현을 해봤는데 한 번에 통과했다.

 

 

 

 

[소스 코드]

N = int(input())
arr = []
count = 0

for _ in range(0, N):
    arr.append(int(input()))

if N > 1:  # 단일 후보일 땐 매수할 필요가 없다.
    while True:
        _max = max(arr)
        if _max > arr[0]:
            idx = arr.index(_max)
            arr[idx] -= 1
            arr[0] += 1
            count += 1
        elif _max == arr[0] and arr.count(arr[0]) >= 2:
            count += 1
            print(count)
            break
        else:
            print(count)
            break
else:
    print(0)

 

리스트 arr을 선언하여 입력받은 득표 수를 전부 담아놓는데, 다솜이의 득표수는 무조건 arr[0]에 저장되어 있을 것이다.

따라서, 다솜이의 득표수 arr[0]이 전체 리스트의 최댓값이 될 때까지 반복을 하고, 반복한 횟수를 출력하면 되는 것이다.

 

매 반복마다 max값의 인덱스 i 를 .index() 함수를 통해 받아오고,

arr[i] = arr[i] -1 / arr[0] = arr[0] +1 연산을 수행한다.

(count 값도 +1 해준다.)

그렇게 arr[0] = max(arr)가 되면 반복을 탈출하고 count를 출력한다.

 

그런데, 아래 예시처럼 최대 득표수가 동률이 될 수도 있다.

이 경우는 다음 두 가지 조건을 만족한다.

- 다솜이의 득표수 == 최대 득표수

- 최대 득표수의 개수 >= 2

 

결국 다솜이가 단독으로 최대 득표자가 되도록 하려는 것이므로, 이 경우에는 1회만 더 반복하면 원하는 결과를 얻을 수 있다.

따라서, count 변수에 +1 연산을 수행한 뒤 반복을 빠져나가버리면 그만이다.

 

---

우선순위 큐 (Priority Queue)

 

문제를 해결하고 며칠 뒤에, 이 문제가 우선순위 큐 알고리즘 문제로 분류되어 있다는 것을 알게 되었다.

그래서 연습 차원으로 우선순위 큐를 사용하여 문제를 다르게 풀어보았다.

 

from queue import PriorityQueue

N = int(input())
dasom = int(input())

result = 0
que = PriorityQueue()

for _ in range(0, N-1):
    val = int(input())
    que.put((-val, val))

while not que.empty():
    temp = que.get()[1]
    if temp >= dasom:
        dasom += 1
        result += 1
        temp -= 1

    if temp >= dasom:
        que.put((-temp, temp))

print(result)

 

 

우선순위 큐는, 큐 안에 들어있는 원소들을 반드시 오름차순으로 정렬된 상태로 유지한다는 특성이 있고, 가장 작은 값부터 꺼낼 수 있다.

 

그래서

- 다솜이의 득표수는 따로 변수를 선언하여 보관.

- 나머지 후보들의 득표수는 우선순위 큐에 입력.

- 큐의 값을 꺼낸 뒤, 다솜이의 득표수와 비교.

  - 꺼낸 값이 만약 다솜이의 득표수보다 크다면, 다솜이의 득표수는 +1, 꺼낸 값은 -1 해준다.

  - 이때, 여전히 꺼낸 값이 다솜이의 득표수보다 크다면 다시 큐에 넣어준다.

 

위 과정을 큐가 텅 빌 때까지 반복하면 원하는 결과를 얻을 수 있다.

 

그런데 한 가지 중요한 점은, 파이썬의 우선순위 큐는 작은 값부터 꺼내서 쓸 수 있다는 것이다.

이 문제에선 작은 값이 아니라 큰 값을 꺼내서 써야 하므로, 우선순위 큐를 역전해서 사용해야 한다.

 

그래서 value를 (-value, value) 형태의 튜플로 만들어서 큐에 put() 하여 구현했다.

값을 꺼내올 땐 que.get()[1]으로, [1]을 붙여주면 된다.

 

 

처음 작성했던 코드에 비해 메모리/시간 둘 다 성능이 떨어진다..

구현을 잘 못해서 그런 건지, 아니면 이게 최선인 건지는 좀 더 연구해봐야겠다.

 

 

참고: 우선순위 큐를 역전하여 사용하는 방법

How to reverse a priority queue in Python without using classes?