백준 9547번 파이썬 | 대통령 선거

문제

대선이 끝난 후 2주가 지났으나 여전히 결과는 발표되지 않았다. 결과가 궁금한 성제는 결과를 직접 미리 알아보기로 했다.

성제는 모종의 방법으로 투표에 참여한 모든 사람들에 대해 한 명도 빠짐없이 선호도 조사를 마쳤다. 성제는 투표에 참여한 사람들이 항상 선호도에 따라 투표했음을 알고 있다.

예를 들어 대통령 후보가 5명이고 어떤 유권자의 선호도가 [3, 2, 5, 1, 4] 인 상태에서 2번 후보와 4번 후보가 경합을 벌인다면, 이 유권자는 2번 후보에게 투표한다.

투표의 전체 규칙은 아래와 같다.

• C명의 후보와 V명의 유권자가 있다. 각 후보는 1에서 C까지의 정수로 표현되며, V는 항상 홀수이다.
• 투표는 2회에 걸쳐 진행된다. 첫 투표에서는 모든 후보가 표를 받을 수 있으며, 만일 이 과정에서 어떤 후보가 모든 표 중 과반수 이상을 획득했다면 그대로 당선되며 투표가 종료된다. 만일 과반수 이상을 획득한 후보가 없다면 가장 많은 표를 받은 두 명만이 2회차에 진출하여 다시 투표를 진행한다. 이 경우엔 2회차에서 과반수 이상의 표를 받은 후보가 최종 당선된다.
• 1회차 투표에서 2등인 후보와 3등인 후보의 득표수는 항상 다르다.
• 유권자는 1회차와 2회차 투표 모두에서 후보들에 대해 동일한 선호도를 갖는다.
• 기권표는 없다.

성제가 조사한 선호도 표에 따라 최종 당선자를 알아내고, 그 당선자가 몇회차 투표에서 당선되었는지 성제에게 알려주도록 하자.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다. ( 1 ≤ T ≤ 100 )

각 테스트 케이스의 첫 줄엔 후보의 수 C와 유권자의 수 V가 주어진다. ( 1 ≤ C, V ≤ 100 )

이어서 V줄에 걸쳐 C개의 정수로 각 유권자의 선호도 표가 주어진다.

가장 처음 주어지는 후보가 가장 선호하는 후보이며, 가장 마지막에 주어지는 후보가 가장 선호하지 않는 후보이다.

선호도 표에는 중복되는 정수가 없으며, 항상 1에서 C까지의 모든 정수를 정확히 한 번씩 포함하고 있다.

출력

각 테스트 케이스마다 당선된 후보의 번호와 투표가 종료된 회차(1 또는 2)를 공백으로 구분하여 출력한다.'

---

풀이

이 문제의 핵심은 dict을 얼마나 잘 활용하는가에 달렸다.

첫번째로 많은 선호도를 가진 후보를 찾는데 이때 과반수 이상이면 바로 출력하고, 아니면 두번째 선호도까지 확인한다.

2등하고 3등과는 득표수가 반드시 다르기 때문에 1,2등으로 선정된 후보들만 저장해서 이 후보들이 나오면 +1점 하는 식으로 더해준다.

문제는 크게 어렵지 않으나 dict을 얼마나 잘 쓰느냐에 따라 구현하는데 많은 시간이 걸렸다..

# 9547 대통령 선거
import sys

T = int(sys.stdin.readline())
for _ in range(T):
    C, V = map(int, sys.stdin.readline().split())
    vote = []
    first = {}
    second = {}
    for _ in range(V):
        vote.append(list(map(int, sys.stdin.readline().rstrip().split())))
    for i in range(V):
        v = vote[i]  # 누가 첫번째 선호도인지.
        if first.get(v[0]):  # 만약에 이미 있는 거면 있는거에 + 1
            first[v[0]] = first[v[0]] + 1
        else:  # 기존에 있는 거면 1로 생성
            first[v[0]] = 1

    Finish = False
    for i, j in first.items():
        if j > V // 2:  # 과반수 이상이면 종료
            print(i, 1)
            Finish = True
    if Finish:
        continue

    WT = sorted(first.items(), key=lambda x: x[1], reverse=True)
    for i in range(2):  # 2등과 3번의 득표수는 항상 다르기에
        second[WT[i][0]] = 0  # 1등하고 2등의 후보가 저장.
    for secv in vote:  # secv는 위에서 입력한 vote 선호순
        for level in secv:  # level은 첫번째 득표번호 -> 두번째 득표수
            # second.key() [0]과 [1]은 1등,2등 후보들인데 나오면 +1점씩
            if level == list(second.keys())[0] or level == list(second.keys())[1]:
                second[level] += 1
                break
    ans = max(second.keys(), key=(lambda x: second[x]))
    print(ans, 2)