Boj 2108 통계학 Python

**정확하지 않은 내용을 담고 있을 수 있습니다**

 

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

 

예전에 풀었던 문제지만 역시나 새롭게 느껴진다.

 

문제는 다음과 같다. 

n개의 입력이 차례대로 주어질 때, 산술평균, 중앙값, 최빈값, 범위를 차례대로 출력하는 문제이다.

 

이때 최빈값의 조건이 조금 까다롭게 느껴질 수 있는데, 최빈값이 2개 이상일 경우에는 그중 두번째로 작은 값을 출력한다는 것이다.

 

처음에는 for문으로 리스트를 순회하며, 각 원소에 대해서 .count연산을 하여 등장횟수를 구하고, 최대 횟수를 저장하였다. 그 후, 최대 횟수만큼 등장한 값들을 배열에 넣고 정렬하여 두번째 값을 출력하였다.

하지만 문제 속 n의 범위는 50만이였고, for문 안에서 count를 시행하는 O(n^2)의 연산은 2초 시간제한으로는 무리였다.

 

때문에 값의 범위가 -4000~4000이라는 것을 감안하여 값에 4000을 더하여 인덱싱을 해준 후, 리스트의 값을 key로, 등장횟수를 value로 갖는 cnt라는 딕셔너리를 만들어서 구현을 하였다.

 

하지만 여전히 시간제한에 걸려 의문을 가졌지만 입력 속도를 높여주니 최종적으로 통과되었다. 다음은 제출한 정답 코드이다.

import sys 
from collections import defaultdict

input = sys.stdin.readline

n = int(input())
l = []
Mc = 0
cnt = defaultdict(int)
ans = set()
for i in range(n):
    a = int(input())
    cnt[a+4000]+=1
    l.append(a)

s = sum(l)
M = max(l)
m = min(l)
for i in range(n):
    Mc = max(Mc, cnt[l[i]+4000])
    
for i in range(n):
    if Mc == cnt[l[i]+4000]:
        ans.add(l[i])
ans = list(ans)
ans.sort()
l.sort()
if s<0:
    print(int(s/n-0.5))
else:
    print(int(s/n+0.5))
print(l[(n-1)//2])
if len(ans)>=2:
    print(ans[1])
else:
    print(ans[0])
print(M-m)

 

그리고 아래는 윗 코드를 기준으로 파이썬 문법을 적용하여 리팩토링 한 버전이다.

import sys 
from collections import defaultdict

input = sys.stdin.readline

n = int(input())
l = []
cnt = defaultdict(int)

for _ in range(n):
    a = int(input())
    cnt[a+4000]+=1
    l.append(a)

s = sum(l)
M = max(l)
m = min(l)
Mc = max(cnt.values())
ans = [k-4000 for k, v in cnt.items() if v == Mc]
ans.sort()
l.sort()

if s<0:
    print(int(s/n-0.5))
else:
    print(int(s/n+0.5))
    
print(l[n//2])

if len(ans)>=2:
    print(ans[1])
else:
    print(ans[0])

print(M-m)

개인적으로 리스트를 순회하지 않고도 최대, 최솟값을 구할 수 있는 코드인

M= max(l)   m = min(l)

그리고 집합의 키와 값을 동시에 반환하는 .items를 이용함과 동시에 조건을 반영하여 대입하는 집약적 문장

 

ans = [k - 4000 for k, v in cnt.items()  if v > Mc]

 

이 가장 인상 깊었다. 파이썬을 사용하며 문제를 풀고 있으니 기왕이면 다른 언어 보다 효율적으로 작성하는 연습을 해야겠다.