Baekjoon 2108번 통계학

문제

https://www.acmicpc.net/problem/2108

걸린 시간

00 : 39 : 01 실패

풀이

Python3

import math

if __name__ == "__main__":
    N = int(input())    

    num = []
    appear = [0] * 8001

    for i in range(0, N):
        temp = int(input())
        appear[temp] += 1
        num.append(temp)

    # 산술 평균
    print(round(sum(num)/N))

    # 중앙값
    num.sort()
    print(num[int(N/2)])

    # 최빈값

    # 1번 이상 입력된 정수만 리스트에 저장
    arr = []
    for i in range(-4000, 4001):
        if appear[i] > 0:
            arr.append([i, appear[i]])    

    # 제일 많이 출현한 횟수
    count = max(arr, key=lambda x:x[1])[1]

    # 최빈값의 후보가 되는 값들을 저장할 리스트
    mode = []

    for i in range(0, len(arr)):
        if arr[i][1] == count:
            mode.append(arr[i])

    # 값을 기준으로 오름차순 정렬
    mode.sort()

    # 정답이 하나만 있다면
    if len(mode) < 2:
        print(mode[0][0])    
    else:
        print(mode[1][0])

    # 범위
    print(max(num)-min(num))

간단한 문제겠거니 하며 효율을 생각하지 않고 코드를 짜다 보니 최빈값을 구하는 부분에서 많은 시간이 걸려 시간초과가 났다.

입력받은 수를 전부 탐색하며 중복된 값이 나올 때 마다 출현 횟수를 세는 알고리즘은 최악의 경우의 수를 계산해본 결과 3,968,004,000 로 어마어마했다.

효율적인 알고리즘이 필요해 문제를 다시 읽어보니 입력받은 정수의 절대값은 4,000을 넘지 않는다는 부분이 눈에 띄었다. 올 수 있는 정수의 개수가 음수, 양수, 0 총 8001개 뿐이라는 것이다. 18111번 마인크래프트 문제에서도 사용되었던 방법으로 배열의 인덱스를 이용해 중복되는 값을 개수로 표시할 수 있었고 최빈값의 후보를 구하는데 드는 경우의 수를 8,001 개로 줄일 수 있었다.