8026 : 허프만 압축
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
문자열이 주어졌을 때, 8비트 ASCII 인코딩으로 저장할 때 필요한 비트 수와 허프만(Huffman) 코딩 알고리즘을 사용하여 최적으로 압축했을 때 필요한 총 비트 수, 그리고 압축률을 계산하는 프로그램을 작성하십시오.
[제약 조건]
• 각 테스트 케이스는 알파벳 대문자 및 밑줄(
• 입력의 마지막 줄에는
• 문자열의 길이는 최대 $1,000$자입니다.
[제약 조건]
• 각 테스트 케이스는 알파벳 대문자 및 밑줄(
_)로 이루어진 문자열입니다.• 입력의 마지막 줄에는
END가 주어집니다.• 문자열의 길이는 최대 $1,000$자입니다.
입력 설명
여러 줄에 걸쳐 테스트 케이스 문자열이 한 줄에 하나씩 주어집니다.
입력의 마지막 줄에는
입력의 마지막 줄에는
END가 주어집니다.출력 설명
각 테스트 케이스에 대해 원래 비트 수, 허프만 압축 비트 수, 압축률(원래 비트 수 / 허프만 비트 수, 소수점 첫째 자리까지 반올림)을 공백으로 구분하여 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
AAAAABCD
THE_ONLY_THING_WE_HAVE_TO_FEAR_IS_FEAR_ITSELF
END
출력 예시
COPY
복사되었습니다!
복사되었습니다!
64 13 4.9
360 124 2.9도움
각 문자의 출현 빈도를 우선순위 큐에 넣고, 가장 작은 두 빈도를 꺼내 합친 뒤 다시 삽입하는 과정을 반복하여 허프만 트리를 생성합니다.
모든 문자가 동일한 1종류의 문자만으로 이루어진 경우 허프만 트리 구성 시 문자당 1비트를 사용하도록 예외 처리해야 합니다.
모든 문자가 동일한 1종류의 문자만으로 이루어진 경우 허프만 트리 구성 시 문자당 1비트를 사용하도록 예외 처리해야 합니다.