[백준][python] 2108번: 통계학

2108번: 통계학

• 백준(boj) 2108번

문제

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

단, N은 홀수라고 가정하자.

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

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

입력 조건

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다.

그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력 조건

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

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

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

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

첫번째 시도. 정렬 알고리즘들의 각기 장단점을 공부하기 이전(2022년 01월 23일)

 import sys
 
 N = int(sys.stdin.readline())
 num = []
 for i in range(N):
     num.append(int(sys.stdin.readline()))
 
 #평균값
 print(round(sum(num)/len(num),0))
 
 #중앙값
 num=sorted(num)
 print(num[int((N-1)/2)])
 
 count=0
 ans=[]
 #최빈값을 구하기 위해 우직하게 두 배열을 순차탐색으로 찾는중...
 for i in num:
   for j in num:
     if i==j:
       count+=1
   ans.append(count)
   count=0
 
 j=0
 new=[]
 #최다 빈도 값을 가려내려는 나의 노력... 이때 왜이랬을까?
 for i in ans:
   if i==max(ans):
     new.append(num[j])
   j+=1
 final=set(new)
 print(final)
 #...
 if len(final)>=3:
   final=list(final)
   final.pop(final.index(min(final)))
   print(min(final))
 else:
   print(max(final))
 
 print(max(num)-min(num))

»output

 Time error

눈물이 앞을 가리는 나의 시도들 1회차…2회차… 모두 fail

🌝 Thinking

알고리즘이 가져다주는 효율성에 대해서 전혀 알지 못하는 상태.

지금도 잘 알고 있는 것은 아니나 기본적이 소양은 지녔다고 생각한다. 조금 더 개선 된 나의 실력으로 짠 코드를 보자.

---

세 번째 시도. (2022년 02월 16일)

 import sys
 input = sys.stdin.readline
 n = int(input())
 # 계수정렬을 이용하여 문제를 접근하였다. 
 # 이유는 절댓값의 크기는 8000이지만 N은 <=500,000 개의 데이터가 주어질 수 있음.
 # 비둘기집의 원리에 의해 숫자들의 빈도수가 높을 것으로 예상. 계수정렬이 어울리겠다!
 
 #음의 값도 처리해주기 위해서 양수음수를 나누어 생각해줌.
 counter_p = [0]*4001
 counter_n = [0]*4001
 
 for i in range(n):
     num = int(input())
     if num >= 0:
         counter_p[num] += 1
     else:
         counter_n[-num] += 1
 
 
 #최빈값을 찾기.
 mod=[]
 if max(counter_n) >= max(counter_p):
     mod_value = max(counter_n)
 else:
     mod_value = max(counter_p)
 
 #최빈값들은 mod배열에 담고, 정렬된 배열은 arr에 담았다.
 arr=[]
 for i in range(4000,0,-1):
     if counter_n[i] == mod_value:
         mod.append(-i)
     for _ in range(counter_n[i]):
         if counter_n[i]!=0:
             arr.append(-i)
 
 for i in range(4001):
     if counter_p[i] == mod_value:
         mod.append(i)
     for _ in range(counter_p[i]):
         if counter_p[i]!=0:
             arr.append(i)        
 
             
 #산술평균
 print(int(round(sum(arr)/n,0)))
 #중앙값
 print(arr[(n-1)//2])
 #최빈값
 if len(mod)==1:
     print(mod[0])
 else:
     print(mod[1])
 #범위
 print(arr[-1]-arr[0])

»input

 5
 -1
 -2
 -3
 -1
 -2

»output

 -2
 -2
 -1
 2

🌝 Thinking

python3로 제출을하면 여전히 시간 초과가 나오지만, pypy3으로 제출 하였더니 success

계수정렬은 리스트의 index가 데이터의 value이고 리스트의 value가 데이터의 빈도수임을 이용한다.

이 문제를 풀때 데이터의 음의 값을 인덱스로 줄수없기에 음의 값만 따로 처리해주는 리스트를 생성해주었다.

---

💡 깨달은 점.

1. 빈도수 관련 문제를 풀거나, 크기가 제한 되어진 데이터를 정렬할때는 계수정렬을 자주 활용해야겠다.