BOJ 5766 - 할아버지는 유명해!

문제

BOJ 5766 - 할아버지는 유명해!

N개의 경주 결과가 주어지고, 각 결과에는 M명의 선수 번호가 순위대로 나열된다. 각 경주에서 1위를 한 선수는 점수를 받지 않고, 나머지 선수들은 순위별 점수를 받는다. 전체에서 2번째로 높은 점수를 가진 선수들의 번호를 출력한다.

입력

• 각 테스트 케이스: 첫 줄에 N M, 다음 N줄에 M명의 선수 번호
• N=0, M=0이면 종료

출력

각 테스트 케이스마다 2번째로 높은 점수를 받은 선수 번호를 공백으로 구분하여 출력한다.

예제

풀이

각 선수의 등장 횟수를 배열로 집계하고, 집합으로 유일한 점수 순위를 구해 두 번째 최댓값에 해당하는 선수를 출력한다.

1. 선수 번호별 카운트 배열 ranking을 10001 크기로 초기화한다.
2. N번의 경주에서 등장하는 모든 선수 번호의 카운트를 증가시킨다 (1위도 포함).
3. set(ranking)으로 유일한 카운트 값을 구하고, 내림차순 정렬하여 두 번째 값(total[1])을 찾는다.
4. ranking 배열에서 해당 카운트와 일치하는 선수 번호를 순서대로 출력한다.

핵심 아이디어: 집합(set)과 정렬로 두 번째 최댓값을 빠르게 구한다. 1위 선수도 카운트에는 포함되므로, 가장 높은 카운트는 1위 선수들의 것이고 두 번째 카운트가 실질적인 정답이다.

코드

import sys
 
input = sys.stdin.readline
 
while True:
    N, M = map(int, input().split())
    if not N and not M:
        break
    ranking = [0] * 10001
    for _ in range(N):
        for i in list(map(int, input().split())):
            ranking[i] += 1
 
    total = sorted(set(ranking), reverse=True)
    second = total[1]
    for i, j in enumerate(ranking):
        if j == second:
            print(i, end=" ")
 
    print()

복잡도

• 시간: O(N)
• 공간: O(N)