[백준 : 5670] 휴대폰자판 - 트라이(Trie)

트라이를 이용한 풀이

import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);

		while (sc.hasNext()) {
			Trie t = new Trie();
			int N = sc.nextInt();
			ArrayList<String> list = new ArrayList<>();
			for (int i = 0; i < N; i++) {
				String input = sc.next();

				t.insertTrie(input);
				list.add(input);
			}
			int sum = 0;
			for (String str : list) {
				sum += t.countClick(str);
			}

			double f = sum / (double) list.size();
			System.out.format("%.2f", Math.round(f * 100) / 100.0);
		}

	}
}

class Trie {
	Trie[] trie;
	int size;

	public Trie() {
		super();
		this.trie = new Trie[26];
		this.size = 0;
	}

	public void insertTrie(String str) {

		Trie child = this;
		for (int i = 0; i < str.length(); i++) {
			if (child.trie[str.charAt(i) - 'a'] == null) {
				child.trie[str.charAt(i) - 'a'] = new Trie();
				child.size++;
			}

			child = child.trie[str.charAt(i) - 'a'];
		}
		child.size++;
	}

	public int countClick(String str) {
		int count = 1;
		Trie child = this;
		for (int i = 0; i < str.length(); i++) {
			if (child.size != 1 && i != 0) {
				count++;
			}
			child = child.trie[str.charAt(i) - 'a'];
		}
		return count;
	}
}