[파이썬/Python] 백준 2108번 통계학

[파이썬/Python] 백준 2108번 통계학

2108번: 통계학

---

문제

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

예제 입력 1

5
1
3
8
-2
2

예제 출력 1

2
2
1
10

풀이 1

import sys
input = sys.stdin.readline

# 입력
n = int(input())
lst = [int(input()) for i in range(n)]

# 1. 산술평균
print(round(sum(lst)/n))

# 2. 중앙값
lst.sort()
print(lst[n//2])

# 3. 최빈값
cnt = dict()
for i in lst:
    if i in cnt:
        cnt[i] += 1
    else:
        cnt[i] = 1

# 최빈값이 여러 개 존재하는 경우
mx = max(cnt.values())
mx_lst = []

for i in cnt:
    if cnt[i] == mx:
        mx_lst.append(i)

# 두 번째로 작은 값을 출력
print(mx_lst[0]) if len(mx_lst) == 1 else print(mx_lst[1])
    
# 4. 범위
print(max(lst)-min(lst))

우선 input() 대신 sys.stdin.readline()을 사용하여 빠르게 입력을 받아왔다.

그리고 수열을 입력받고, 각각의 값을 구하기 위해 다음과 같은 방법을 사용하였다.

산술평균 : 수열의 합을 n으로 나눈 값을 출력하며, round() 함수를 사용하여 반올림한다.
중앙값 : 수열을 오름차순으로 정렬한 후, 가운데 위치한 값을 출력한다. 홀수 개의 데이터일 경우 중앙값은 하나의 값이며, 짝수 개의 데이터일 경우 중앙값은 가운데 두 값의 평균이다.
최빈값 : dict() 자료형을 사용하여 각 수가 나타난 횟수를 세고, 가장 많이 나타난 값을 출력한다. 최빈값이 여러 개 존재하는 경우에는 그 중에서 두 번째로 작은 값을 출력한다.
범위 : 최대값에서 최소값을 빼서 출력한다.

 

시간 복잡도 관점에서 보면, 입력 받는 부분의 시간 복잡도는 O(n)이다. 그리고 수열의 합을 구하는 부분은 O(n)이다. 수열을 정렬하는 부분은 파이썬 내장 함수인 sorted()를 사용하였으므로 시간 복잡도는 O(n log n)이다. 최빈값을 구하는 부분은 각 수가 나타난 횟수를 세는 과정에서 O(n)의 시간 복잡도가 들어가며, 가장 많이 나타난 값들을 구하기 위해서는 최대값을 찾는 과정에서 O(n)의 시간 복잡도가 들어가게 된다. 따라서, 최빈값을 구하는 부분의 시간 복잡도는 O(n)이다. 마지막으로, 범위를 구하는 부분은 최대값과 최소값을 구하는 과정에서 O(n)의 시간 복잡도가 들어간다.

 

더 효율적인 코드를 제시하자면, 최빈값을 구하는 부분에서 collections 모듈의 Counter() 함수를 사용하면 더 간단하게 구현할 수 있다. 이 함수는 리스트의 각 요소의 개수를 세어서 딕셔너리 형태로 반환해준다. 따라서, 다음과 같은 코드로 최빈값을 구할 수 있다.

 

풀이 2

위에서 Counter() 함수를 사용하여 cnt 변수에 딕셔너리 형태로 각 요소의 개수를 저장하였다. 이를 활용하여 최빈값을 구하려면, most_common() 함수를 사용하면 된다. 이 함수는 딕셔너리의 요소를 개수가 많은 순으로 정렬한 후, 튜플 형태로 반환한다. 반환된 튜플의 첫 번째 요소는 딕셔너리의 키 값이며, 두 번째 요소는 딕셔너리의 값(개수)이다.

따라서, 최빈값을 구하는 부분은 다음과 같이 구현할 수 있다.

import sys
from collections import Counter
input = sys.stdin.readline

# 입력
n = int(input())
lst = [int(input()) for i in range(n)]

# 1. 산술평균
print(round(sum(lst)/n))

# 2. 중앙값
lst.sort()
print(lst[n//2])

# 3. 최빈값
cnt = Counter(lst)
mode = cnt.most_common()

if len(mode) == 1 or mode[0][1] != mode[1][1]:
    print(mode[0][0])
else:
    print(mode[1][0])

# 4. 범위
print(max(lst)-min(lst))

most_common() 함수를 호출하여 반환된 결과를 mode 변수에 저장한다. 그리고 mode 변수의 길이가 1이거나 첫 번째 요소의 개수와 두 번째 요소의 개수가 다른 경우에는 첫 번째 요소의 키 값을 출력하면 된다. 그렇지 않은 경우에는 두 번째 요소의 키 값을 출력하면 된다.

이렇게 구현하면, 최빈값을 구하는 부분의 시간 복잡도는 O(n log n)에서 O(n)으로 개선된다. 따라서, 전체 코드의 시간 복잡도는 O(n log n)에서 O(n)으로 개선된다.

 

 

참고자료

[백준] 2108번 : 통계학 (파이썬)