백준 2108번 : 통계학

문제.

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

2108번: 통계학

 

아이디어 :

시간제한 2초 = 8000만번 연산 가능

O(N^2) = 250억번 >>> 8000만번 -> 불가

O(NlogN) = 약 300만번 < 8000만번 이므로 O(NlogN)가능

가능한 최대 원소 개수 = 50만개, 가능한 원소의 종류 = 8001개

정렬할 전체 원소 개수 >> 원소 종류의 개수 이므로 계수 정렬

 

 

구현 :

import sys
n = int(input())
arr = []
cnt = [0] * 8001 # idx - 4000 = 수
for i in range(n) :
  num = int(sys.stdin.readline().strip())
  arr.append(num)
  cnt[num+4000] += 1

arr.sort()
avg = sum(arr)/len(arr)
mid_idx = ((len(arr)+1) // 2) - 1 
range_n = max(arr) - min(arr)

def most_frequency(cnt) :
  most_fre = []
  same = cnt.count(max(cnt)) # 최빈값의 등장 빈도수
  if same == 1 : # 최빈값과 등장 빈도수가 동일한 원소 개수가 1개
    most_n = cnt.index(max(cnt))-4000
  else : #  최빈값과 등장 빈도수가 동일한 원소 개수가 2개 이상
    j = 0
    while same >= 1 :
      if max(cnt) == cnt[j] :
        most_fre.append(j-4000)
        same -= 1
      j += 1
    most_fre.sort()
    most_n = most_fre[1]
  return most_n

print(round(avg))
print(arr[mid_idx])
print(most_frequency(cnt))
print(range_n)

 

총평 :

정렬과 구현(최빈값 출력)을 합쳐놓은 문제였다.

풀고나서 보니 어차피 계수정렬을 사용할 거 였으면 굳이  입력받은 원소arr에 전부 저장하지 않고

cnt 리스트만을 이용해서도 구현 가능했을 것 같다.

시간과 공간 복잡도가 좀 더 타이트한 기준이었다면 그렇게 했을 것 싶다.

(대신 arr에 저장하고 sort를 했기 때문에 산술평균, 중앙값, 범위 구하는 식이 조금 더 간편해진 것도 맞다)