[파이썬] 2108번 : 통계학

https://www.acmicpc.net/problem/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

예제 입력 2 복사

1
4000

예제 출력 2 복사

4000
4000
4000
0

예제 입력 3 복사

5
-1
-2
-3
-1
-2

예제 출력 3 복사

-2
-2
-1
2

 

생각

산술평균

- 입력받은 수의 합을 구하고 처음에 입력받은 수로 나누어주면 되겠구나 그런데 반올림을 해야하니 round함수를 쓰자

 

중앙값

- 입력받은 수를 정렬한 것을 가지고 처음에 입력받은 수를 2로 나눈 몫을 인덱스로 이용하면 되겠다.

 

최빈값

-입력받은 수 중에 가장 많이 나타나는 값을 해야한다.

생각을 해보면 입력받은 것이 중복이 될 수도 있다 이때 중복이 되었으면 그 갯수를 늘려야 한다. 그래서 zip함수를 이용하는데 list로 감싸자라는 접근을 하였다

이때 인자는 iterable객체여야 하니 첫번째 인자로는 입력받은수의 중복을 제거한 집합을 가지고 하고, 두번째 인자는 이 집합의 갯수만큼 0을 가지고 있는 리스트를 하나 만들어서 넣는다.  

이렇게 하면 리스트안에 튜플로 감싸진 2개의 값이 (입력한 값 , 입력한 값의 갯수) 형태로 저장된다. 이것을 앞의 형태의 인덱스 1을 기준으로 오름차순 정렬을 하고, 인덱스 0을 기준으로 두번째 정렬을 해버린다.

그런데 여기서 입력한 값의 갯수가 같은 경우에는 2번째로 작은 값을 출력하라고 했으니 이것을 고려해서 하면 된다.

 

범위출력

- max값과min값간의 차이를 구하면 되겠다 -> 그런데 정렬된 것을 가지고 인덱스 0과 -1을 이용해서 하면 편리하겠다.

 

import sys
num=int(sys.stdin.readline())
nums=[int(sys.stdin.readline()) for _ in range(num)]
nums=sorted(nums)
print(round(sum(nums)/num)) #산술평균
print(nums[(num//2)]) #중앙값

#최빈값
set_nums=list(set(nums))
count_list=[0 for _ in range(len(set_nums))]
for i in nums:
    count_list[set_nums.index(i)]+=1
list_nums=list(zip(set_nums,count_list))
list_nums=sorted(list_nums,key=lambda x:(x[1],x[0]))
list_nums=list_nums[list_nums.index(max(list_nums, key=lambda x: x[1])):]
if len(list_nums)>1:
    print(list_nums[1][0])
else:
    print(list_nums[0][0])

print(nums[-1]-nums[0]) #범위출력

이거의 경우 시간초과가 났다.

왜 일어났나 여러가지를 시도하면서 해봤는데 전체적으로 보면 반복문이 하나만 있어 O(n)에 해당하는 시간복잡도를 가지고 있다고 할 수 있다. 하지만 넣을 수 있는 데이터의 갯수는 50만개에 해당하고 나올 수 있는 정수는 8000개에 해당하게 된다. 그러면 총 20억개에 해당하는 연산이 이뤄지는 꼴이 된다. 왜냐하면 for문을 돌때에는 50만개지만 8000개에 해당하는 index함수를 하게 된다음 +1즉 counting을 하면서 연산이 이뤄지기 때문이다. 

그리고 sort를 하는 부분에 있어서 O(nlogn)에 해당하는 것이 든다. 하지만 위의 것보다는 시간이 덜 소요된다고는 할 수 있지만 영향이 없는 것은 아니다. 

 

그래서 collections 모듈의 Counter 클래스를 쓴다.

import sys
from collections import Counter
n = int(sys.stdin.readline())
nums = []
for i in range(n):
    nums.append(int(sys.stdin.readline()))
nums.sort()
nums_s = Counter(nums).most_common()
print(round(sum(nums) / n))
print(nums[n // 2])
if len(nums_s) > 1:
    if nums_s[0][1] == nums_s[1][1]:
        print(nums_s[1][0])
    else:
        print(nums_s[0][0])
else:
    print(nums_s[0][0])
print(nums[-1] - nums[0])

데이터의 개수가 많은 순으로 정렬된 배열을 리턴하는 most_common이라는 메서드라는 것을 활용.

 

또는 Counter클래스를 쓰지 않고선,

import sys
arr=list()
dic=dict()
for _ in range(int(sys.stdin.readline())):
    num=int(sys.stdin.readline())
    arr.append(num)
    if dic.get(num,False):
        dic[num]+=1
    else:
        dic[num]=1
arr.sort()
print(round(sum(arr)/len(arr)))
print(arr[len(arr)//2])
max_value=dic[max(dic,key=lambda x:dic[x])]
max_arr=sorted([key for key in dic if dic[key] == max_value])
print(max_arr[1 if len(max_arr) > 1 else 0])
print(arr[-1]-arr[0])

사전자료형에 max함수를 적용한다면 key값이 들어가서 max key값이 나오게 된다 이걸 이용해서 lambda함수의 인자로 들어오는 것은 key값이기 때문에 dict[x]로 value가 큰 값을 반환하게 한다.

접근 방법은 애초에 처음입력할때 배열과 사전으로 나눠서 입력을 하게 되는 것이다.

그런데 여기에서도 counting에 해당하는 +1을 하게 되는데 이것은 시간초과가 걸리지 않는 다는 것은 set을 쓰고 sorted를 하는 과정에서 nlogn에 해당하는 시간복잡도지만 이것도 많은 영향을 끼쳤다는 것을 생각하게 되었다.