BOJ. Phone Keyboard (5670)

Problem: BOJ 5670 — Phone Keyboard

For each word, the first letter is always typed. After that, type the next letter only when the current trie node has more than one child, or the current prefix is itself a complete word. A complete word needs this extra keystroke to distinguish it from longer words with the same prefix.

Insert all words before counting keystrokes. Each trie node records its number of distinct child nodes and whether it ends a word. Thus duplicate insertions do not create extra branches, while a prefix-word collision is counted through the end-of-word flag. Sum each word’s keystrokes and divide by the number of words in that dataset; print each average with exactly two decimal places.

The trie construction and all word traversals take O(S) time, where S is the total number of characters across the input words. The trie uses O(S) nodes (with 26 child references per node), and the input words are retained for counting.

Java

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		Trie trie;
		ArrayList<String> al = new ArrayList<>();
		while(true) {
			String ss = br.readLine();
			if(ss == null || ss.length() == 0) break;
			int n = toi(ss);
			if(n == 0) break;
			trie = new Trie();
			al.clear();

			for(int i = 0; i < n; i++) {
				String s = br.readLine();
				trie.add(s);
				al.add(s);
			}
			int count = 0;
			for(String s: al) {
				count += trie.solve(s);
			}
			sb.append(String.format(Locale.ROOT, "%.2f", (double)count / n)).append("\n");
		}
		print(sb);
	}

	static class Trie {
		Trie[] arr = new Trie[26];
		int num = 0;
		boolean tail;

		void add(String s) {
			int l = s.length();
			Trie t = this;
			for(int i = 0; i < l; i++) {
				int ch = s.charAt(i) - 'a';
				if(t.arr[ch] == null) {
					t.arr[ch] = new Trie();
					t.num++;
				}
				t = t.arr[ch];
			}
			t.tail = true;
		}

		int solve(String s) {
			Trie t = arr[s.charAt(0) - 'a'];
			int cnt = 1;

			for(int i = 1; i < s.length(); i++) {
				if(t.num + (t.tail ? 1 : 0) > 1) cnt++;
				t = t.arr[s.charAt(i) - 'a'];
			}
			return cnt;
		}
	}

	static int toi(String s) { return Integer.parseInt(s); }
	static String[] getLine() throws IOException { return br.readLine().split(" "); }
	static int[] getArr() throws IOException { return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); }
	static <T> void print(T s) { System.out.print(s); }
	static <T> void println(T s) { System.out.println(s); }
}