[BOJ] 2108 통계학 - python

백준 2108번 통계학 문제이다.

계속해서 시간 초과가 나서 좀 오래 걸렸다.

최빈값을 구하는 부분에서 계속 시간 초과가 발생했다.

 

1차 코드

N = int(input())
array = []

for _ in range(N):
    array.append(int(input()))

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

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

# 최빈값
dict = {}
# 전체 리스트의 값 별로 개수를 세어 딕셔너리 형태로 저장한다.
for _ in array:
    dict[_] = array.count(_)
# value값을 기준으로 내림차순으로 정렬한다.
sorted_dict = sorted(dict.items(),key = lambda item: item[1], reverse=True)
if len(sorted_dict) <= 1:
    print(array[0][0])
elif sorted_dict[0][1] == sorted_dict[1][1]:
    print(sorted_dict[1][0])
else:
    print(sorted_dict[0][0])

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

 

2차 코드

인터넷을 참고하니 대부분 counter를 사용했다. 

그러나 라이브러리 없이 풀고 싶어 for문을 사용하여 다시 작성했다.

지금보니 for + sort로 오히려 시간 복잡도를 더 늘려놨다...ㅎㅎ

저 때는 아무 생각 없었다.........

+) 파이썬 sorted와 sort의 시간복잡도는 모두 O(nlogn)이라고 한다.

N = int(input())
array = []

for _ in range(N):
    array.append(int(input()))

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

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

# 최빈값
dict = {}
# 전체 리스트의 값 별로 개수를 세어 딕셔너리 형태로 저장한다.
for _ in array:
    dict[_] = array.count(_)
# dict의 value중 최대값의 key들을 모아 max_list에 저장한다.
max_list = [k for k,v in dict.items() if max(dict.values()) == v]
max_list.sort()
if len(max_list) > 1:
    print(max_list[1])
else:
    print(max_list[0])

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

 

input도 sys.stdin.readline으로 바꿔봤지만 똑같았다...

 

3차 코드 - 최종

결국 counter를 사용했다...

import sys
from collections import Counter

N = int(sys.stdin.readline())
array = []

for _ in range(N):
    array.append(int(sys.stdin.readline()))

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

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

# 최빈값
# array 리스트의 값과 개수를 딕셔너리 형태로 저장해준다.
common = Counter(array).most_common()
if len(common) > 1 and common[0][1] == common[1][1]:
    print(common[1][0])
else:
    print(common[0][0])

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