SWExpert Academy: 1204. 최빈수 구하기

#sw_expert_academy #Algorithm #D2 #Solved
문제 링크

제한사항

• 시간 : 10개 테스트케이스를 합쳐서 C의 경우 10초 / C++의 경우 10초 / Java의 경우 20초 / Python의 경우 30초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

문제 정리

가장 큰 최빈수를 구하라.

접근 방법

최빈수는 해당 숫자가 가장 많이 나올 때 최빈수가 된다.
최빈수인지 확인하기 위해선 숫자의 출현 빈도를 따로 저장할 필요성이 있다.
생각나는 선택지는 2가지. map과 단순 int 배열. map은 해싱 비용도 있으므로 int 배열 사용했다. [^1]

 

문제에서 최빈수가 여러 개면 가장 큰 점수를 출력하라는 조건이 있다.

선행 검색 중에 최빈값의 출현 빈도가 현재 최빈값과 같으면 해당 값을 최대 최빈값으로 설정한다.

복잡도

시간복잡도: O(score_max)
공간복잡도: O(score_max)

코드

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
output = ""
for test_case in range(1, T + 1):
    test_case_no = int(input())
    score_counts = [0] * 101
    for num in list(map(int, input().split())):
        score_counts[num] = score_counts[num] + 1
    max_count = 0
    max_score = 0

    for score, cnt in enumerate(score_counts):
        if cnt >= max_count:
            max_count = cnt
            max_score = score
    output += f"#{test_case} {max_score}\n"
print(output)

 

후기

지금 코드를 다시 보는데, for문 하나로 해결 가능해보인다. 그래도 가독성까지 생각하면 위처럼 for문 두 개 쓰는 게 나아보인다.

어차피 최대 점수가 100점이므로 아무리 반복문이 많이 돌아도 100번 + 100번. 이 정도 연산은 가독성을 살리는 게 이득이라고 생각한다.

 

[^1]: 단, 만약 최대 점수가 500만 이러면 map을 쓰는 게 낫다. map의 공간 복잡도는 주어진 점수의 개수지만, int 배열은 score 만점이 공간복잡도다.