[백준/알고리즘/python/java] 1417번 - 국회의원 선거

이미지를 누르면 문제링크를 보실 수 있습니다.

이미지를 누르면 문제링크를 보실 수 있습니다.

정답률이 낮은 이유는 아마 제출 수가 적은 것도 그렇지만, 예외처리 때문일 것이다.

나도 한 2번 틀리고 반례를 발견했으니 말이다.

우선, 시간제한도 2초로 넉넉한 편이어서 for문이나 while문 사용에 거부감이 없었다.

이번 코드리뷰는 내가 제출했었던 코드들을 순차적으로 살펴보자.

 

맨 처음 제출해서 틀렸던 코드는 아래와 같다.

import sys
input = sys.stdin.readline

n = int(input())
vote_list = []
count = 0

for i in range(n):
    vote_list.append(int(input()))
dasom = vote_list[0]
not_dasom = sorted(vote_list[1:], reverse=True)
print(not_dasom[0]-dasom)

문제의 로직은 입력받은 int형 리스트의 0번째 원소가 다솜이의 투표수이고, 1번째 원소부터가 다른 후보들의 투표수이다. 후보군의 투표수를 리스트로 저장하기 위해서 1번째 원소부터 끝 원소까지 슬라이싱을 하고, 내림차순으로 역순정렬하였다.

그러면, 후보군 투표수 리스트의 0번째 원소는 후보군 중에 가장 많은 득표를 한 후보일 것이고 다솜이는 그 후보를 제쳐야만 당선이 될 것이다. 그래서 단순히 후보군 중 득표수가 가장 많은 후보와 다솜이의 투표수를 뺀 값을 출력하도록 하였다.

반례가 아직 존재했는데, 대표적으로, 다솜이만 출마할 경우도 있다. 그럴 때는, 인덱싱 오류가 나버린다. 다솜이 혼자 출마하는 경우를 고려하여 고친 코드는 아래와 같다.

import sys
input = sys.stdin.readline

n = int(input())
vote_list = []
count = 0

for i in range(n):
    vote_list.append(int(input()))
if n == 1:
    print(0)
else:
    dasom = vote_list[0]
    not_dasom = sorted(vote_list[1:], reverse=True)
    print(not_dasom[0]-dasom)

하지만, 반례가 아직 존재했다. 예를 들어, 5 7 7 7 이라는 vote_list를 입력받았다면, 다솜이가 당선이 되기 위한 최소 투표 조작수는 2장이 아닌 3장이 필요했다. 단순히 뺀다고 해결되는 문제는 아니었다.

사실, 이전에 while문과 for문을 먼저 시도해서 비교하면서 푸는 문제라고 생각했는데, '내림차순' 이라는 방법이 생각나고 너무 단순하게 생각했던 것 같다.

 

다시 최종적으로 고친 코드는 아래와 같다.

import sys

input = sys.stdin.readline

n = int(input())
vote_list = []
count = 0

for i in range(n):
    vote_list.append(int(input()))
if n == 1:
    print(0)
else:
    dasom = vote_list[0]
    not_dasom = sorted(vote_list[1:], reverse=True)
    for index, num in enumerate(not_dasom):
        if dasom == num:
            print(1)
            break
        while(not_dasom[0] >= dasom):
            count += 1
            dasom += 1
            not_dasom[0] -= 1
            not_dasom = sorted(not_dasom, reverse=True)
        print(count)
        break

사실, for문에서 index나 enumerate도 안쓰인다. 처음에 의도했던 코드에서 '내림차순'이 생각나서 그냥 바로 쓴 코드이다. 단순히, not_dasom 리스트만 for문으로 순회하는 문제이다.

이 때, not_dasom(다른 후보군) 중에 가장 많은 투표수를 얻은 후보군이 다솜이와 같은 투표수라면 1장만 받아도 되므로, 1을 출력하고 프로그램을 종료한다.

그렇지 않다면, while문에서 후보군의 첫번째 값, 즉 후보군 중 가장 많은 득표수와 다솜이의 득표 수를 비교하여, 다솜이가 비로소 해당 후보보다 득표가 많아질 때, 비로소 while문을 탈출하도록 한 코드이다.

while문안에서는 단순히, 출력해야하는 count를 하나씩 증가시켜주고, 다솜이의 득표수는 1씩 증가시켜준다.

그리고 가장 많은 득표수의 다른 후보의 수는 그대로 1씩 감소시켜주되, 다시 reverse()로 내림차순으로 재정렬한다. 그래야, 그 때 그 때 바뀌는 최고 득표자 후보군과 다솜이의 득표수를 비교할 수 있기 때문이다.

 

생각했던 반례는 다음과 같다.

다솜이를 포함한 전체 후보자들의 정수형 입력 리스트가 

5 7 2 일 때, 2가 정상적으로 출력되었고 5 7 7 7 일 때, 3이 정상적으로 출력되었다.

중간에, 5 7 7 7 반례에서 2가 출력되어서 왜 그런가 싶었는데, 역순으로 정렬할 때, not_dasom 이라는 변수에 할당을 안해주고 단순히 정렬만 시켜서 그랬었다. 다시 변수에 할당해주는 것을 항상 잊지말자!