[백준 14725번] 개미굴 (java)

14725번: 개미굴

 

 

트라이를 사용하여 문제를 해결하였다.

 

보통은 트라이노드의 Key값에 char형을 넣지만, 이 문제에서는 두 번째 예제의 경우 문자열이 하나의 노드에 들어가야 하므로 char형이 아닌 String형으로 변경하였다. 또한, 문제에서 알파벳 순서대로 출력해야 하므로 자식 노드들 중 알파벳 순서상 앞에 위치한 노드부터 탐색해야 한다. 따라서 TreeMap을 사용하여서 자동으로 알파벳 순으로 정렬되도록 했다.

Map<String, TrieNode> childNodes = new TreeMap<>();

 

Trie 클래스에 print()라는 메서드를 추가해서 자식노드를 탐색하는 과정에서 문제의 출력형식대로 출력하도록 했다. print()의 매개변수로는 현재 노드의 높이 정보(floor)를 넣어서 높이에 따라 '--'가 다르게 출력되도록 했다. 예를 들어, 높이가 1이면 '--'만 출력되고, 높이가 2라면 '----'가 출력되어야 한다.

public void print(TrieNode thisNode, int floor) {

		Set<String> set = thisNode.getChildNodes().keySet();
		Iterator<String> it = set.iterator();

		while (it.hasNext()) {
			String str = it.next();

			TrieNode childNode = thisNode.getChildNodes().get(str);
			for (int i = 0; i < floor; i++)
				System.out.print("--");
			System.out.println(str);
			print(childNode, floor + 1);

		}
}

 

문제예제에서 각 줄마다 K개만큼의 문자를 입력받으면 그 문자들을 StringBuffer을 이용하여 하나로 합쳐주었다. 그리고 이 StringBuffer을 트라이에 삽입한다.

여기까지는 트라이의 일반적인 삽입과정과 동일하나, 한가지 다른점이 있다면 이 문제에서는 각 노드에 들어가는 것이 Character형이 아니라 String형이라는 점이다. 두 번째 예제에서 "APPLE" "BANANA" "KIWI"를

StringBuffer로 합치면 "APPLEBANANAKIWI" 가 된다. 하지만 어디서 어디까지의 문자열이 하나의 노드에 들어가는지에 대한 정보가 없다. 따라서 트라이에 삽입할 때, 문자열을 어디어디서 끊어줄지에 알려주기 위해 각 문자열의 길이 정보도 함께 넘겨주었다.

 

첫번째 문자열(APPLE)은 길이가 5이므로 arr[0] = 5가 된다. 두번째 문자열(BANANA)는 길이가 6이므로 arr[1] = 6이 된다.세번째 문자열(KIWI)는 길이가 4이므로 arr[2] = 4가 된다.

 for (int i = 0; i < N; i++) {
		String[] input = br.readLine().split(" ");

		int K = Integer.parseInt(input[0]);
		int[] arr = new int[K];

		StringBuffer buf = new StringBuffer();
		for (int j = 1; j <= K; j++) {
			buf.append(input[j]);
			arr[j - 1] = input[j].length();
		}

		trie.insert(buf.toString(), arr);

 }

 

그러면, insert() 메서드 내에서는 이 길이정보를 가지고 전체 문자열 "APPLEBANANAKIWI"을 적당히 끊어서 각각의 트라이 노드에 넣어준다.

APPLE / BANANA / KIWI

   public void insert(String word, int[] arr) {

		TrieNode thisNode = rootNode;

		int idx = 0;
		for (int i = 0; i < arr.length; i++) {
			String str = word.substring(idx, idx + arr[i]);
			idx = idx + arr[i];

			thisNode = thisNode.getChildNodes().computeIfAbsent(str, key -> new TrieNode());
		}
		thisNode.setIstLastChar(true);
   }

 

 

전체코드 :