백준 5670번 휴대폰 자판 (JAVA)

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

5670번: 휴대폰 자판

 

플래티넘이라는 난이도에 비해서는 그다지 어렵지 않은 문제였다고 생각한다.

Trie 알고리즘을 사용해 풀 수 있는 전형적인 문제였다.

public class BOJ_5670_휴대폰자판 {
	static Function<String, Integer> stoi = Integer::parseInt;
	static int N;
	static Trie root;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str;
		while ((str = br.readLine()) != null) {
			N = stoi.apply(str);
			root = new Trie();
			List<String> words = new ArrayList<>();
			for (int i = 0; i < N; i++) {
				words.add(br.readLine());
				parse(words.get(words.size() - 1));
			}
			float sum = 0;
			for (String word : words) {
				sum += root.find(word);
			}
			System.out.printf("%.2f\n", sum / words.size());
		}
	}

	private static void parse(String s) {
		Node node = root.data;
		for (int i = 0; i < s.length(); i++) {
			node = node.children.computeIfAbsent(s.charAt(i), c -> new Node());
		}
		node.end = true;
	}

	static class Trie {
		Node data;

		Trie() {
			data = new Node();
		}

		int find(String s) {
			int sum = 1;
			Node node = data;
			for (int i = 0; i < s.length(); i++) {
				char c = s.charAt(i);
				node = node.children.get(c);
				if (i < s.length() - 1 && (node.end || node.children.size() > 1)) {
					sum++;
				}
			}
			return sum;
		}

	}

	static class Node {
		Map<Character, Node> children;
		boolean end;

		Node() {
			this.children = new HashMap<Character, Node>();
			end = false;
		}
	}
}