[백준 6800] Huffman Encoding (JAVA)

 

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

6800번: Huffman Encoding

 

이번에 다뤄볼 문제는 문자열을 다루는 문제이다.

 

처음 문제를 봤을때 그림때문에 트리문제인가 싶어 풀었지만,

 

트리문제라기보단 그냥 문자열 문제에 가깝다.

 

각 알파벳은 이진트리에 따라 분류되어 0과 1로 이루어진 유일한 코드를 갖는다.

 

이런 알파벳이 코드와 함께 주어질때 코드로만 이루어진 문자열이

어떤 알파벳문자열을 의미하는지 출력해주면 되는 문제이다.

 

 

문제를 해결하는 아이디어는 간단하다. 문자열의 앞에서부터 차례로 현재 입력받은 알파벳의 코드중일치하는 것이있나

검사하고 그만큼 문자열을 자르기를 반복하기만 하면된다.

 

그럼 바로 코드로 옮겨 보도록 하겠다.

 

입력받는 알파벳과 코드는 각각 문자열 배열에 저장할것이다.

 

		int k = Integer.parseInt(in.readLine());
		String[] letter = new String[k];
		String[] huffmanCode = new String[k];

 

그리고 주어지는 코드도 변수에 저장해준다.

 

		String code = in.readLine();

 

다음은 위에서 언급한 반복의 과정이다.

 

1. 문자열의 왼쪽에서부터 코드와 일치하는것이있나 검사

2. 문자열 자르기

3. 모든 문자열을 자를때까지 반복

 

		while(code.length() > 0) {
			int i = 0;
			while(!code.startsWith(huffmanCode[i])) {i++;}
			sb.append(letter[i]);
			code = code.substring(huffmanCode[i].length());
		}

 

 

이미 startsWith 이라는 좋은 메소드가 있기때문에 그냥 사용해주면 된다.

 

예제의 실행결과는 잘 나온다.

 

 

아래는 코드의 전문이다.

 

package boj4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj6800 {
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int k = Integer.parseInt(in.readLine());
		String[] letter = new String[k];
		String[] huffmanCode = new String[k];
		
		for(int i = 0; i < k; i++) {
			st = new StringTokenizer(in.readLine()," ");
			letter[i] = st.nextToken();
			huffmanCode[i] = st.nextToken();
		}
		
		String code = in.readLine();
		
		in.close();
		
		while(code.length() > 0) {
			int i = 0;
			while(!code.startsWith(huffmanCode[i])) {i++;}
			sb.append(letter[i]);
			code = code.substring(huffmanCode[i].length());
		}
		
		System.out.print(sb);
	}

}