[백준] 5670번 : 휴대폰 자판 - 자바(Java)

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

5670번: 휴대폰 자판

 

문제 해석

hello, hell, heaven, goodbye라는 단어가 있습니다.

이때 입력을 더 빨리 받기 위해 자동입력을 지원해줍니다.

만약 h를 누르게 된다면 h로 시작하는 모든 단어가 he를 가지기 때문에 자동으로 e를 입력해줍니다.

이후에 a를 누르게되면 hea -> 이후로 단어는 heaven이 유일하므로 heaven이 자동완성됩니다. (2번만에 완성)

he 상태에서 l을 누르게 되면 hello와 hell 에서 hell이 공통적인 단어이므로 l이 자동으로 입력됩니다.

hell은 (2번만에 완성됩니다 h입력(1) l입력(2))

이후에 o를 누르게 되면 hello가 완성되고 hello는 3번만에 완성됩니다

g로 시작하는 단어는 유일합니다 따라서 g만 1번 입력하게 되면 goodbye가 완성됩니다.

 

따라서 모든 단어의 평균을 내면 hello(3) + hell(2) + heaven(2) + goodbye(1) = 8/4 = 2.00입니다.

문제 풀이전 설계

트라이 자료구조를 사용하는 문제 같습니다.

우선 단어들을 모두 트라이 자료구조에 저장합니다.

그리고 단어가 끝나는 지점을 체크합니다.

그리고 자식이 2개이상이라면 사용자의 입력을 기다려야 하므로 이때도 count를 증가시킵니다.

 

코드

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

public class Main_5670_휴대폰자판 {

    static class Node {

        HashMap<Character, Node> childs = new HashMap<>();
        boolean isCount;

    }

    static class Trie{
        Node root;

        public Trie(Node root) {
            this.root = root;
        }

        public void insert(String word){
            Node tempNode = this.root;
            for(int i=0; i< word.length(); i++){
                tempNode = tempNode.childs.computeIfAbsent(word.charAt(i), c -> new Node());
            }
            tempNode.isCount = true;
        }

        public double getCount(String word){
            //첫번째는 무조건 입력을 받음
            double count = 1.0d;
            Node tempNode = this.root;
            tempNode = tempNode.childs.get(word.charAt(0));
            
            for (int i = 1; i < word.length() ; i++) {
                //자식이 2개 이상이면 count
                if(tempNode.childs.size() >=2){
                    count+= 1.0d;
                //마지막 노드가 아닌데 체크되어있다면 count    
                } else if(tempNode.childs.size()==1 && tempNode.isCount){
                    count+= 1.0d;
                }
                char ch = word.charAt(i);
                Node node = tempNode.childs.get(ch);
                tempNode = node;
            }

            return count;
        }
    }


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

        while ((num = br.readLine()) != null) {
            if(num.equals(""))break;
            int N = Integer.parseInt(num);
            String cur = null;
            String[] words = new String[N];
            Trie root = new Trie(new Node());
            for (int i = 0; i < N; i++) {
                cur = br.readLine();
                root.insert(cur);
                words[i] = cur;
            }
            double avg = 0.0d;
            for (String e : words) {
                avg += root.getCount(e);
            }
            avg = avg / N;
            sb.append(String.format("%.2f",avg) + "\n");
        }
        System.out.print(sb.toString());


    }
}