통계학

성공한 코드

import sys
from collections import Counter

input = sys.stdin.readline

N = int(input())
li = [int(input()) for _ in range(N)]

li.sort()

many = Counter(li)
cnt = many.most_common(2)
avg = sum(li)/N
print(round(avg))
print(li[(N - 1)//2])
if len(cnt) > 1 and cnt[0][1] == cnt[1][1]:
    print(cnt[1][0])
else:
    print(cnt[0][0])
print(li[N - 1] - li[0])

문제 해결 포인트

1. python은 코드 작성도 중요하지만, 라이브러리를 잘 가져다 쓰는게 중요하다 느꼈다.
2. 최빈값을 구하는데에 이중 반복문이 들어가는 구현은 시간초과를 유발한다 생각했고, 최빈값을 구하는 기능을 제공하는 Counter class의 내장함수를 사용하기로 결정했다.
3. python3보다 반복적인 코드를 사용하는 pypy3의 장점을 살렸다.

   python3 vs pypy3
   PyPy3에서는 실행시, 자주 쓰이는 코드를 캐싱하는 기능이 있다.
   즉, 메모리를 조금 더 사용하여 그것들을 저장하고 있어, 실행속도를 개선할 수 있다.
   간단한 코드상에서는 Python3가 메모리, 속도 측에서 우세할 수 있는 것이고,
   복잡한 코드(반복)을 사용하는 경우에서는 PyPy3가 우세하기 때문에 코드 상황에 맞추어 두 구현체(PyPy3, Python3)를 적절하게 사용하는 것이 효율적이라고 할 수 있다.
   출처

li = [0,0,1]
many = Counter(li)
print(many)
#Counter({0: 2, 1: 1})
cnt = many.most_common(2)
print(cnt)
#[(0, 2), (1, 1)]
#만약 li = [0,0,0]이었다면
#[(0, 3)] 으로 2개를 요청해도 하나만 나온다.

위와 같은 특성을 살려서 cnt의 개수가 1개 초과라면 2개라는 것이고 그 조건에 최빈값이 같다면 2번째 인자를 출력 아니라면 첫번째 인자(가장 많이 나온 수)를 출력해 주었다.

내가 작성한 코드보다 압도적으로 빠른 속도로 평가가 진행되는 것을 보고 "문제 해결 포인트"의 첫번째 조건의 중요성을 다시 한번 느꼈다.

실패한 코드

import sys
input = sys.stdin.readline

def findM(li, i, len):
    idx = i
    while(idx < len and li[idx] == li[i]):
        idx += 1
    return idx - i

N = int(input())
gap = 0
beforegap = 0
many = 0
many2 = 0
li = [int(input()) for _ in range(N)]

li.sort()

for i in range(N):
    gap = findM(li, i, N)
    if gap >= beforegap:
        if gap == beforegap and many2 == 0:
            many = 0
            many2 = li[i]
        elif gap > beforegap:            
            many = li[i]
            many2 = 0
        beforegap = gap
    i += gap

avg = sum(li)/N
print(round(avg))

print(li[(N - 1)//2])

if many:
    print(many)
else:
    print(many2)

print(li[N - 1] - li[0])

1. 최빈값을 구하기 위해 count를 사용했더니 2%에서 시간초과가 발생했다. count는 list의 전체를 훑기때문에 비효율적이다. 이미 sort를 통해 정렬을 하였으니 최빈값을 찾으려는 타겟의 값에대한 이전에 찾은 값 혹은 현재 값과 같지않은 값이 나오면 그 개수가 해당 값의 개수이고, 이미 찾은 인덱스 값들을 다시 조회하지 않도록 for문 내의 i에 찾은 개수를 추가해주었다.
2. 두번째의 최빈값을 구하기 위해 list에 개수가 같은 값들을 저장한뒤 index = 1의 값을 출력하려 했으나, append()로 추가하며 시간소요가 발생하여 변수 2개를 사용하여 값을 구해주었다.

1 번을 적용시켰을 때 40% 통과되었고, 2번까지 적용시키자 42%통과되었다.

주의사항

• 평균값은 반올림하여 계산한다.
• 최빈값의 개수가 동일한 것이 여러개라면 두번째로 작은 수를 선택한다.

함수 호출시간을 줄이기 위해 findM()함수를 메인문에 포함시킨 코드

import sys
input = sys.stdin.readline

N = int(input())
gap = 0
beforegap = 0
many = 0
many2 = 0
li = [int(input()) for _ in range(N)]

li.sort()

for i in range(N):
    idx = i + 1
    while idx < N and li[i] == li[idx]:
        idx += 1
    gap = idx - i

    if gap >= beforegap:
        if gap == beforegap and many2 == 0:
            many = 0
            many2 = li[i]
        elif gap > beforegap:            
            many = li[i]
            many2 = 0
        beforegap = gap
    i += gap

avg = sum(li)/N
print(round(avg))
print(li[(N - 1)//2])
if many:
    print(many)
else:
    print(many2)
print(li[N - 1] - li[0])

이 코드 역시 42%에서 시간초과 발생

결과