[boj 4419] Austrailam Voting

문제 링크

 

영어 문제라는 점에서 1차 난관, 구현 문제라는 점에서 2차 난관...

 

그냥 구현하면 되는 문제라 설명이 필요한가 싶다. 다만 주의점이 2가지 있다.

1. 브루트포스로 접근하면 시간초과 주의

2. 최저점은 여러명이 될 수 있음을 주의

 

이것만 주의하면서 풀면 될 듯 하다.

 

나는 이걸 제대로 처리 못해서 여러번 틀렸다...

 

 

import sys
input = sys.stdin.readline


def solve():
    N = int(input())

    num_to_name = {}
    for i in range(1, N + 1):
        num_to_name[i] = input().rstrip()

    is_available = [1] * (N + 1)

    total_num = 0
    candidates = [()]
    while True:
        line = input()
        if not line:
            break
        candidate = tuple(map(int, line.split()))
        if not candidate:
            break
        candidates.append(candidate)
        total_num += 1

    half = total_num // 2 + 1

    cnt = [0] * (N + 1)
    state = [[] for _ in range(N + 1)]

    # 초기 1순위 집계
    for idx in range(1, total_num + 1):
        first = candidates[idx][0]
        cnt[first] += 1
        state[first].append(idx)

    idxs = [0] * (total_num + 1)   # 각 투표지가 현재 가리키는 순위 인덱스

    while True:
        alive = [i for i in range(1, N + 1) if is_available[i]]

        max_val = max(cnt[i] for i in alive)
        min_val = min(cnt[i] for i in alive)

        # 과반 승자
        if max_val >= half:
            for i in alive:
                if cnt[i] == max_val:
                    print(num_to_name[i])
                    return

        # 전원 동률
        if max_val == min_val:
            for i in alive:
                print(num_to_name[i])
            return

        min_idxs = [i for i in alive if cnt[i] == min_val]

        # 같은 라운드에서 탈락하는 후보들 먼저 전부 비활성화
        for idx in min_idxs:
            is_available[idx] = 0

        # 탈락 후보들의 표 재분배
        for idx in min_idxs:
            for s in state[idx]:
                while True:
                    idxs[s] += 1
                    if idxs[s] >= len(candidates[s]):
                        break

                    nxt = candidates[s][idxs[s]]
                    if is_available[nxt]:
                        cnt[nxt] += 1
                        state[nxt].append(s)
                        break

            cnt[idx] = 0
            state[idx] = []


def main():
    solve()


if __name__ == "__main__":
    main()

저는 바보입니다...