[BOJ] 2108 - 통계학

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

2108번: 통계학

import sys
from collections import Counter
n = int(sys.stdin.readline())
data = []
for i in range(n):
    data.append(int(sys.stdin.readline()))
    
data.sort()
avg = sum(data) / len(data) # 산술 평균
mid = data[(n - 1) // 2] # 중앙값

most_nums = Counter(data).most_common()
print(most_nums) 
        
print(round(avg))  # round 함수로 반올림
print(mid)

if len(most_nums) > 1:  # 최빈값
    if most_nums[0][1] == most_nums[1][1]:
        print(most_nums[1][0])
    else:
        print(most_nums[0][0])
        
else:
    print(most_nums[0][0])
    
print(abs(data[n - 1] - data[0]))

이 문제는 단순히 산술평균, 중앙값, 최빈값, 최댓값과 최솟값의 차이 등 다양한 수학적인 값들의 출력을 요구하는 정렬 문제이다.

그럼에도 불구하고 이 문제를 리뷰하는 이유는 전 포스트를 통해 공부한 시간 제한을 고려하여 코드를 짜는 연습을 하기 위함이고 이 문제를 처음 풀었을 때 시간 초과 판정을 받아서 시간 단축을 위해 노력이 필요했기 때문이다.

또한 Counter 클래스의 most_common 메소드의 사용법을 정리하기 위함이다.

 

먼저 n의 범위가 1 <= n <= 500,000 이었기 때문에 2초에 40,000,000번의 연산을 할 수 있는 파이썬 기준으로 O(nlogn) 정도의 효율이 필요하다는 것을 알 수 있다.

 

※ 수행 시간을 줄인 부분

• 입력받는 부분은 input() 대신 sys.stdin.readline() 사용
• 최빈값 구하는 부분에서 count() 함수 대신 collections.Counter 클래스의 most_common 메소드 사용

most_nums = Counter(data).most_common()

if len(most_nums) > 1:  # 최빈값
    if most_nums[0][1] == most_nums[1][1]:
        print(most_nums[1][0])
    else:
        print(most_nums[0][0])
        
else:
    print(most_nums[0][0])

위는 collections.Counter 클래스의 most_common 메소드를 사용해 최빈값을 구하는 코드이다.

most_common(n) 메소드는 가장 많이 등장한 n개의 원소를 리스트에 담긴 사전 자료형 형식으로 개수가 많은 순 정렬하여 리턴해주는 함수이다 (n을 생략하면 모든 원소를 추출한다). 반환된 형식은 [(원소, 개수)]이다. 즉, most_num[1][0]은 최빈값 중 두 번째로 작은 값이 되는 것이다.

 

시간 제한이 엄청 엄격한 문제는 아니라서 이 정도 개선으로도 통과할 수 있었다. 하지만 sum() 함수 대신 입력받을 때 합을 같이 더해준다거나 리스트 대신에 사전 자료형을 이용하는 등으로 시간을 더 줄이는 방법도 있었다.