★ solved.ac 난이도 : S4
(작성 시점 기준)
[문제 본문 링크]
5230번: Prefix Codes
The first line in the test data file contains the number of test cases (< 100). After that, each line contains one test case. The test case begins with k, the number of strings to be decoded, the string representation of the prefix code, followed by the k
www.acmicpc.net
이 문제는 이진 트리에 저장된 문자열 데이터를 바탕으로 2진수로 된 코드의 디코딩을 구현하는 문제입니다.
(허프만 트리와 유사합니다.)
1차원 배열로도 풀 수 있으며, 해결 방법은 어렵지 않다고 생각합니다.
(문제 본문이 영어로 되어있어서 이해가 어려울 수도 있습니다.)
트리 데이터를 배열로 입력받고 2진수 코드의 값에 따라 좌우로 적절히 이동하면서 문자를 만날 때마다 만난 문자를 출력하는 과정을 반복하면 됩니다. 문자를 출력 후에는 트리의 첫 부분으로 이동해야 합니다.
PS. 이 문제의 최초 정답자입니다.
[소스 코드 (C++98)]
★ 틀린 점이 있다면 알려주세요~!