백준 #3161 izbori

문제 링크

[1761 izbori]

문제 설명

$N$명의 후보자를 $M$명의 투표자가 각 후보자에 대한 선호도를 나타내고있다. 각 후보자는 어떤 후보자에 대해 그 후보자보다 선호도를 높게 받은 수가 많을 경우 1점을 획득한다 점수가 가장 높거나 같은 후보자를 구하는 문제

코드

import sys
input = sys.stdin.readline
from collections import defaultdict

M, N = map(int, input().split())
arr = [[0] * (N + 1) for _ in range(N + 1)]
votes = [list(map(int, input().split())) for _ in range(M)]
for vote in votes:
    visited = [False] * (N + 1)
    for x in vote:
        visited[x] = True
        for i in range(1, N + 1):
            if not visited[i]:
                arr[x][i] += 1
win_cnt = [0] * (N + 1)
for i in range(1, N + 1):
    for j in range(i + 1, N + 1):
        if arr[i][j] > arr[j][i]:
            win_cnt[i] += 1
        elif arr[i][j] < arr[j][i]:
            win_cnt[j] += 1

max_v = max(win_cnt)
for i in range(N + 1):
    if win_cnt[i] == max_v:
        print(i)

풀이

$N\times N$행렬을 만들어 준 뒤에 각 쌍의 후보자에 대해서 이긴 횟수를 기록해준다. 마지막에는 각 쌍의 후보자 중 이긴 후보자에 대해 1점을 부여해주고 점수가 가장 높거나 같은 후보자들을 출력해준다!