[ BOJ 오답노트 ] 2108 파이썬 : 통계학

2022 02 19

 

1. 틀린 기록

 

 

 

2. 원인 분석

- 시간 초과 판정이 났다. 한 2%까지 채점되다가 시간초과가 딱 떠버린게 네번이다. ㅎㅎ

- 문제 풀이 중에서 최빈값 (가장 많이 나온 값)을 찾는 부분에서 'count' 함수를 사용한 것이 시간초과의 원인이었다.

 

- count 함수는 O(N)의 복잡도를 가지지만, 내가 짠 코드에서는 while 문 안에서 계속 선형 탐색하면서 연산하기 때문에 O(N^2)까지 연산량이 증가한 것으로 보인다. 

- 그래도 내 나름대로 i += count를 해주어서 그 다음 값이 현재 값과 같다면 굳이 확인하지 않아도 되게 설계했지만, 어차피 count 함수는 연산 중에 인덱스 0부터 끝까지 연산하기 때문에 의미가 없었던 것이다.

 

 

 

3. 해결

import sys
input = sys.stdin.readline

n = int(input())
lst = []

for _ in range(n):
    lst.append(int(input()))

countLst = []
lst.sort()

# 산술평균
print(round(sum(lst) / n))


# 중앙값
print(lst[n//2])


# 최빈값
i = 0
while i < n:
    count = 1
    val = lst[i]

    for j in range(i+1, n, 1):
        if val == lst[j]:
            count += 1
        else:
            break
    i += count
    countLst.append([val, count])


countLst.sort(key=lambda x: (-x[1], x[0]))

if n == 1:
    print(countLst[0][0])
elif countLst[0][1] == countLst[1][1]:
    print(countLst[1][0])
else:
    print(countLst[0][0])

# 범위
print(max(lst) - min(lst))

 

 

 

4. 배운 점

- count 함수가 가장 효과적일 것이라고 생각했지만, 어차피 처음부터 끝까지 반복하면서 개수를 센다는 것을 간과하고 있었던 것 같다.

- 이번 문제에서 하도 lambda를 많이 써서 이제 문법을 확실히 익히는 계기가 되었다.