[백준] 2108 통계학 파이썬 딕셔너리

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

2108번: 통계학

import sys
N = int(sys.stdin.readline())

n_list = []
for i in range(N):
    n_list.append(int(sys.stdin.readline()))

n_list.sort()

counts = {}
for i in n_list:
    if i in counts:
        counts[i] += 1
    else:
        counts[i] = 1

counts = sorted(counts.items(), key=lambda counts: counts[1], reverse=True)



print(int(round(sum(n_list)/len(n_list), 0)))

print(n_list[len(n_list)//2])
if N != 1 and counts[0][1] == counts[1][1]:
    print(counts[1][0])
else:
    print(counts[0][0])

print(max(n_list) - min(n_list))

이번 문제는 진짜 오래걸렸다... 계속해서 시간초과가 발생했다.

처음 코드를 짰을 때는 for문을 이용해서 최빈값을 구했는데 N이 최대 500000까지 들어갈 수 있기 때문에 시간초과가 발생했다. 이를 해결하기 위해서 별 방법을 다 써봤지만 모조리 실패했다.

그간 틀린 흔적들이다. 시간 초과를 벗어나기 위해서는 리스트 전체를 도는 것을 벗어나야만 했기 때문에 처음 낸 아이디어는 -4000부터 4000까지만 for문을 돌려 count 하는 방식이었다.

 

import sys
N = int(sys.stdin.readline())

n_list = []
for i in range(N):
    n_list.append(int(sys.stdin.readline()))

n_list.sort()

count_list = []
count = 0 
for i in range(-4000, 4000):
    if n_list.count(i) > count:
        count_list = []
        count_list.append((n_list.count(i), i))
        count = n_list.count(i)
    elif n_list.count(i) == count:
        count_list.append((n_list.count(i), i))
    

print(int(round(sum(n_list)/len(n_list), 0)))

print(n_list[len(n_list)//2])
if len(count_list) == 1:
    print(count_list[0][0])
else:
    print(count_list[1][0])

print(max(n_list) - min(n_list))

이게 그 코드다. 카운트를 해서 카운트 리스트를 만들어줬는데 여기서 append를 하는 과정 때문인지 여전히 시간초과가 발생했다. 그렇게 한참을 고민하던 도중 리스트보다 딕셔너리가 탐색에 있어서 속도가 빠르다는 사실을 기억해냈다.

 

딕셔너리는 해싱방식을 이용하기 때문인데 key가 있기 때문에 그 key값을 이용하여 value를 찾아 리스트 전체를 돌며 찾는 리스트에 비해 속도가 빠른것이다. 모든 경우 그런 것은 아니라고 하니 조금 더 깊게 공부해봐야 할 것 같다.

 

아무튼 딕셔너리를 이용하여 코드를 짜봤다. counts라는 딕셔너리에 카운팅을 해주며 값을 찾았고 이를 lambda식을 이용해 솔팅해줬다. 결과는 정답이었다.

 

왜이렇게 정답률이 낮을까 했는데 낮을 수 밖에 없는 문제였다. 오히려 27%의 정답률이 신기했다.

 

다른 사람들의 풀이를 보니 counter라는 것을 이용했는데 어떻게 이런 함수를 알고 쓰는건지... 신기하다. 그래도 오기가 생겨서 딕셔너리로 스스로 풀어내고 나니 뿌듯한 것 같다.