엔트로피

면접 대비

시간 제한1초메모리 제한128 MB

요약

한 줄의 문자열을 읽고 각 문자의 등장 횟수를 세어 섀넌 엔트로피를 소수점 셋째 자리까지 반올림해 출력한다.

난이도: 쉬움10점 중 2점
유형: 해시맵, 수학, 구현, 문자열
정답자: 아직 제출이 없습니다

문제

1948년 클로드 섀넌(Claude E. Shannon)은 논문 통신의 수학적 이론(The Mathematical Theory of Communication)에서 이산 확률 분포 $p_1, \ldots, p_n$ 의 엔트로피를 정의하는 유명한 공식을 제시했다.

$H = -\sum_{i} p_i \log_2 p_i.$

이 공식을 문자열에 적용하기 위해, $p_i$ 를 문자열에서 각 문자가 등장하는 상대 빈도로 둔다. 예를 들어 길이가 38인 문자열 Northeastern European Regional Contest(공백 3개 포함)의 엔트로피는 소수점 아래 셋째 자리까지 반올림하면 $3.883$ 이다. 아래 표는 이 문자열의 각 문자에 대한 상대 빈도 $p_i$ 와 엔트로피의 각 항 $-p_i \log_2 p_i$ 를 보여 준다.

문자	등장 횟수	$p_i$	$-p_i \log_2 p_i$	문자	등장 횟수	$p_i$	$-p_i \log_2 p_i$
공백	3	$0.079$	$0.289$	i	1	$0.026$	$0.138$
C	1	$0.026$	$0.138$	l	1	$0.026$	$0.138$
E	1	$0.026$	$0.138$	n	4	$0.105$	$0.342$
N	1	$0.026$	$0.138$	o	4	$0.105$	$0.342$
R	1	$0.026$	$0.138$	p	1	$0.026$	$0.138$
a	3	$0.079$	$0.289$	r	3	$0.079$	$0.289$
e	5	$0.132$	$0.385$	s	2	$0.053$	$0.224$
g	1	$0.026$	$0.138$	t	4	$0.105$	$0.342$
h	1	$0.026$	$0.138$	u	1	$0.026$	$0.138$

주어진 문자열의 엔트로피를 계산하라.

입력

입력은 한 줄로 이루어지며, 길이가 1 이상 1000 이하인 문자열이 주어진다. 문자열의 각 문자는 0–9, a–z, A–Z, .(마침표), 공백 중 하나이다. 앞, 중간, 뒤에 오는 공백도 모두 문자열의 일부이다.

출력

입력 문자열의 엔트로피 $H = -\sum_{i} p_i \log_2 p_i$ 를 한 줄에 출력한다. 여기서 $p_i$ 는 각 문자의 상대 빈도이다. 답은 소수점 아래 셋째 자리까지 반올림하여 출력한다.

예제7

예제 1

입력

Northeastern European Regional Contest

예상 출력

3.883

예제 2
입력
```
a
```
예상 출력
```
0.000
```
예제 3
입력
```
ab
```
예상 출력
```
1.000
```
예제 4
입력
```
abcd
```
예상 출력
```
2.000
```
예제 5
입력
```
0123456789
```
예상 출력
```
3.322
```
예제 6
입력
```
aaaabbbbccccdddd
```
예상 출력
```
2.000
```
예제 7
입력
```
Hello World
```
예상 출력
```
2.845
```