[Baekjoon 2108 / Python / 실버3] 통계학

문제

# 구현, 수학, 정렬

import sys

input = sys.stdin.readline

N = int(input()) # 수의 개수, 홀수

number = []

for _ in range(N):

    number.append(int(input()))

if N == 1: # 수가 1개일 경우

    print(f'{number[0]}\n{number[0]}\n{number[0]}\n0')

else: # 수가 3개 이상일 경우

    number.sort()

    # 최빈값 구하기, 첫번째 숫자 넣어놓고 시작한다

    result = [number[0]]

    curCnt = 1

    maxCnt = 1

    # 리스트를 한번 순회하며 최빈값을 찾는다

    for i in range(1, N):

       

        if number[i] == number[i-1]: # 이전 숫자와 같을 경우 카운트 추가

            curCnt += 1

            if curCnt == maxCnt: # 최빈값이 겹칠 경우 append 한다

                result.append(number[i])

            elif curCnt > maxCnt: # 최빈값이 갱신되었다면 대체한다

                result = [number[i]]

                maxCnt = curCnt

       

        else: # 새로운 숫자일 경우 카운트 초기화

            curCnt = 1

            if curCnt == maxCnt: # 최빈값이 겹칠 경우 append 한다

                result.append(number[i])

   

   

    print(round(sum(number) / N)) # 평균

    print(number[N//2]) # 중앙값

    # 최빈값

    if len(result) > 1:

        result.sort()

        print(result[1])

    else: print(result[0])

    print(number[-1] - number[0]) # 범위

 
구현, 수학, 정렬 문제이다.
 
수를 입력받고 평균, 중앙값, 최빈값, 범위를 모두 출력하면 되는 문제이다. 최빈값을 제외하면 그냥 바로 출력만 해도 된다. 최빈값을 효율적으로 찾는 것이 관건인 문제이다.
 
N의 범위는 50만개다. 즉 수의 개수가 50만개이며, 모든 숫자를 하나하나 count 함수를 이용해 최빈값을 찾게 되면 최악 시간 복잡도가 O(N^2)이 나와버린다. 50만 곱하기 50만이면 2500억번 연산을 하게 된다. 이건 절대 정답이 아닐 것이다.
 
그래서 최빈값 찾기 연산이 O(N) 복잡도를 가지도록 리스트를 한번만 순회하며 최빈값을 찾도록 구현했다. 
result 리스트에 최빈값들을 담을 것이고, 시작할 때 첫번째 숫자를 미리 담아두고 시작한다.
계산에 사용될 변수 curCnt, maxCnt도 1로 초기화해두고 시작한다. 각각 현재 카운트, 최대 카운트를 저장한다.
 
number 리스트는 어차피 정렬되어 있기 때문에, 같은 값은 무조건 연속적으로 등장한다. 따라서 이전 값과 비교해서 같을 경우 curCnt를 추가해 주고 maxCnt와 비교해서 result 리스트에 추가해 주거나 대체해주면 된다.
 
결과적으로 이 문제의 최악 시간 복잡도는 O(N log N)이다. 그 이유는 파이썬 sort() 내장함수의 Timsort 정렬 알고리즘의 복잡도가 O(N log N)이기 때문이다. Timsort 정렬 알고리즘은 병합 정렬과 삽입 정렬의 하이브리드 방식이다.
 
 
 

결과