[Baekjoon | 백준] 2108번. 통계학 (파이썬/정렬, Counter 사용법)

문제

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

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

 

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

 

예제 입력 1

5
1
3
8
-2
2

 

예제 출력 1

2
2
1
10

 

예제 입력 2

1
4000

 

예제 출력 2 

4000
4000
4000
0

 

알고리즘 분류

• 정렬
• 수학
• 구현

 

풀이 방식

중앙값을 구하는 부분에서 정렬을 사용하고 나머지는 그냥 구현을 하면 되는 문제이다. 최빈값을 구하는 부분이 조금 구현하기가 어려웠다.

 

입력 조건

입력 조건에 N은 앞으로 몇 줄을 받을지에 대한 것인데 이것이 500,000이므로 sys모듈을 사용해야 함을 알 수 있고 O(N^2) 풀이는 불가능 하다는 사실을 알 수 있다.

 

 

1번 풀이: 실패

 

최빈값: N개의 수들 중 가장 많이 나타나는 값

 

처음 생각한 풀이는 가장 많이 나타났는 지를 알기 위해서 collections 모듈의 Counter를 활용하여 각 숫자들의 갯수를 dictionary 형태로 변환 후 이를 다시 key, value 쌍의 리스트로 변환하여 for문을 돌면서 가장 많이 나온 수이면서 그 갯수를 가진 수가 또 있으면 그 다음으로 큰 수를 출력하는 식으로 코드를 작성하였다.

 

import sys
from collections import Counter
input = sys.stdin.readline

N = int(input())

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

print(sum(arr)//N)

arr.sort()
print(arr[N//2])

freq = Counter(arr)
tmp = []
for k, v in freq.items():
    tmp.append([k, v])
tmp.sort(key=lambda x: x[1])
min_val = float('inf')
for k, v in tmp:
    min_val = min(min_val, v)

count = 0
for i in tmp:
    if i[1] == min_val and count == 0:
        count += 1
    elif i[1] == min_val and count > 0:
        print(i[0])
        break

print(max(arr)-min(arr))

하지만 이는 예제 2번 테스트 케이스를 통과하지 못하는데 가장 빈도가 높은 숫자가 하나인 경우에 제대로 동작하지 않기 떄문이다.

 

 

2번 풀이: 성공

그래서 생각한 것은 dict를 리스트로 변환한 후 value에 해당하는 값으로 내림차순 soring 하고 같으면 key에 해당하는 값으로 오름차순 sorting을 하고 분기를 하여 케이스에 맞게 구현하였다.

만약 리스트의 크기가 1개라면 해당 원소가 최빈값이므로 리스트의 크기가 2 이상이면서 가장 빈도수가 높은 원소와 같은 갯수의 원소가 존재한다면 두 번째로 작은 원소를 출력하도록 하고 그렇지 않으면 첫번째 원소를 출력하도록 한다.

import sys
from collections import Counter
from math import ceil
input = sys.stdin.readline

N = int(input())

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

print(round(sum(arr)/N))

arr.sort()
print(arr[N//2])

freq = Counter(arr)
tmp = []
for k, v in freq.items():
    tmp.append([k, v])
tmp.sort(key=lambda x: (x[1], -x[0]), reverse=True)
# print(tmp)
if len(tmp) >= 2 and tmp[0][1] == tmp[1][1]:
    print(tmp[1][0])
else:
    print(tmp[0][0])

print(max(arr)-min(arr))

 

 

most_common()을 사용한 풀이

from collections import Counter

numbers = []
for _ in range(int(input())):
    num = int(input())
    numbers.append(num)

numbers.sort()

cnt = Counter(numbers).most_common(2)

print(round(sum(numbers) / len(numbers)))
print(numbers[len(numbers) // 2])
if len(numbers) > 1:
    if cnt[0][1] == cnt[1][1]:
        print(cnt[1][0])
    else:
        print(cnt[0][0])
else:
    print(cnt[0][0])
print(max(numbers) - min(numbers))

 

 

Counter

 

파이썬 collections는 기본 내장 모듈로써 deque, Counter 등과 같이 굉장히 유용한 함수들을 제공한다.

기본적인 사용법은 위 코드에서 처럼 Counter() 함수 안에 인자로 넣은 값에 대해 빈도수를 측정하여 key, value 쌍의 딕셔너리로 반환하는 역할을 한다.

 

>>> Counter(["hi", "hey", "hi", "hi", "hello", "hey"])
Counter({'hi': 3, 'hey': 2, 'hello': 1})

 

해당 사용법에 대해 자세히 알고 싶으면 help 함수를 통해 출력해 보면 다양한 사용법과 예제를 에디터에서도 볼 수가 있다.

from collections import Counter
print(help(Counter))

 

 

여기서 유용한 메서드가 하나 존재한다.

 

most_common()

가장 빈도수가 높은 원소 N개를 리스트 형태로 반환하는 함수로 안에 인자로 값을 아무 것도 적지 않으면 전부다 나오게 되고 안에 적은 인자 수만큼 빈도수 순서대로 리스트의 원소로 반환하게 된다. 

>>> c.most_common(3)                # three most common elements
[('a', 5), ('b', 4), ('c', 3)]

해당 메소드가 유용한 이유는 초기 Counter 반환 상태는 아무런 정렬이 되지 않은 상태인데 most_common을 사용하여 값을 재 반환하면 알아서 정렬이 되기 때문에 빈도수가 높은 것부터 순서대로 무언가를 하고 싶을 때 사용하면 굉장히 유용하다.

 

만약 상위 3개를 뽑으려 하는데 Counter 객체에 key, value 쌍이 2개 이하가 존재한다 하더라도 오류가 나지 않고 딱 있는 갯수만큼만 리턴을 해 준다.

 

from collections import Counter

c = Counter("abcdeabcdabcaba")
sorted_c = sorted(c)
print(sorted_c)
# ['a', 'b', 'c', 'd', 'e']

Counter 객체를 sorted 함수를 거쳐 반환하게 되면 unique한 요소들을 담은 리스트를 반환하는 것이 가능하다.(dict는 unique key이기 때문)

 

print(''.join(sorted(c.elements())))
# 'aaaaabbbbcccdde'

elements()는 기존 값의 원소를 모두 반환하여 join, sort와 함께 사용하여 문자열 정렬이 가능하다.

 

print(sum(c.values())
# 15

values()의 sum을 구하면 모든 counts의 갯수를 반환할 수 있다.

 

d = Counter("simsalabim")
c.update(d)
print(c['a'])
# 7

새로운 counter를 기존의 counter에 update 하는 것도 가능하다. a의 갯수가 5개에서 9개로 증가한 것을 확인할 수 있다.

 

print(Counter('abbb') + Counter("bcc"))
# Counter({'b': 4, 'c': 2, 'a': 1})

Counter 끼리 덧셈 연산을 진행하면 count 횟수끼리 더하게 된다. 일종의 합집합 연산이라고 보면 될 것 같다.

 

 print(Counter('abbb') & Counter('bcc'))
# Counter({'b': 1})

물론 & 연산자를 통해 교집합(Intersection)을 구하는 것도 가능하다.

 

print(Counter(a=1, b=2) - Counter(a=4, b=1))
# Counter({'b': 1})

'-' 연산을 진행하는 경우 뒤의 Counter에 더 많은 갯수가 있으면 그 element는 사라지게 된다.

 

c = Counter('which')
c.subtract('witch')
print(c) # Counter({'h': 1, 'w': 0, 'i': 0, 'c': 0, 't': -1})
c.subtract(Counter('watch'))
print(c) # Counter({'h': 0, 'i': 0, 'w': -1, 'c': -1, 'a': -1, 't': -2})

하지만 subtract 메서드를 사용하면 사라지지 않고 값이 negative(음수)로 변환이 된다.

그래서 사용하고자 하는 용도에 따라 맞는 것을 사용하면 된다.