[HackerRank] Tree: Huffman Decoding

자료구조에 익숙해지기 위해 HackerRank 문제들을 공부중이다. 그 중 미디움 난이도 트리문제를 보면서 재미있었던 문제가 바로 이 문제이다. 허프만 디코딩 문제는 트리를 순회하면서 이진 문자열을 디코딩하는 문제이다. 

 

1100 순으로 순회하면 C라는 문자와 대응된다. 출처 : HackerRank

 

문제를 접근한 전략은 간단했다. 이진 문자열을 부분으로 자르면서 대응되는 문자가 있는지 없는지 찾아보는 것이다. 부분 문자열의 길이를 늘려가면서 트리를 순회하면 비교적 간단하게 풀이할 수 있는 문제였다.

 

void decode(String s, Node root) {

        String answer = "";
        String target = "";

        while (s.length() > 0) {

            for (int idx = 1; idx <= s.length(); idx++) {

                Node head = root;
                target = s.substring(0, idx);

                for (char t : target.toCharArray()) {
                    if (head != null) {
                        if (t == '0') {
                            head = head.left;
                        }
                        else if (t == '1') {
                            head = head.right;
                        }
                    }
                }

                if (head.data != 0) {
                    String changed = Character.toString(head.data);
                    answer += changed;
                    s = s.substring(idx, s.length());
                    idx = 0;
                }
                
            }
        }

        System.out.println(answer);
            
    }

 

주의할 점은 for문을 돌면서 idx가 증가한다는 것과 부분 문자열로 자를 때 인덱스 계산을 잘 해줘야 한다는 점이다. 이 두 부분을 디버깅하는데 시간을 오래 썼지만 접근방법은 유효했다.