백준 : 5670

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

5670번: 휴대폰 자판

 

재미있는 Trie 문제이다.

 

자식을 HashMap으로 나타내어 접근하기 쉽게 하였다.

 

문제에서 cnt를 +1 할지 cnt로 갈지 cnt를 1로 갈지를 잘설정하여 DFS에 넘겨주면된다. 

 

1. rootTrie를 설정한다.

2. insert를 통해서 chlid들을 만든다. 이때 현재노드의 자식수를 만든다.

3. serach를 통하여 모든 root를 탐방한다. 이때 현재 keyPushCnt를 만들어서 dfs탐색을 한다.

4. 현재 push가 0인경우 다음 pushCnt 는 무조건 1

5. 현재 자식수가 1이면서 현재 root가 끊나면 cnt + 1, 끊나지않앗으면 cnt

6. 자식이 없으면 return

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

public class B5670 {
	static int N;

	static class TrieNode {
		HashMap<Character, TrieNode> children;

		boolean isEndOfWord;
		int childCnt;

		public TrieNode() {
			childCnt = 0;
			isEndOfWord = false;
			children = new HashMap<Character, TrieNode>();
		}
	}

	static TrieNode root;

	static void insert(String key) {
		int level;
		int length = key.length();

		TrieNode pCrawl = root;

		for (level = 0; level < length; ++level) {
			if (!pCrawl.children.containsKey(key.charAt(level))) {
				pCrawl.children.put(key.charAt(level), new TrieNode());
				pCrawl.childCnt++;
			}
			pCrawl = pCrawl.children.get(key.charAt(level));
		}

		// for이 다놀고나면 가장 끝에 노드까지 다만들어진다.
		// pCrawl 은 end 노드

		pCrawl.isEndOfWord = true;

	}

	static double allWordCnt;

	static void search(TrieNode curNode, int cnt) {
		if (curNode.isEndOfWord) {
			allWordCnt += cnt;
		}

		if (curNode.childCnt == 0) {
			return;
		} else if (curNode.childCnt == 1) {
			Iterator<Character> keys = curNode.children.keySet().iterator();
			TrieNode next = curNode.children.get(keys.next());
			if (cnt == 0)
				search(next, 1);
			else if (curNode.isEndOfWord) {
				search(next, cnt + 1);
			} else
				search(next, cnt);
		} else {
			Iterator<Character> keys = curNode.children.keySet().iterator();
			while (keys.hasNext()) {
				TrieNode next = curNode.children.get(keys.next());
				search(next, cnt + 1);
			}
		}

	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		String line = null;
		StringBuilder sb = new StringBuilder();

		while ((line = br.readLine()) != null) {

			int N = Integer.parseInt(line);
			allWordCnt = 0;

			root = new TrieNode();

			for (int n = 0; n < N; n++) {
				String key = br.readLine();
				insert(key);
			}

			// 평균을 구한다.
			search(root, 0);
			double ans = allWordCnt / N;
			sb.append(String.format("%.2f", ans)).append('\n');
		}
		System.out.println(sb.toString());

	}
}