📖 [백준알고리즘 풀이] Q.5670 휴대폰 자판 문제 풀이 - java

📖 문제

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

휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발하였다. 이 모듈은 사전 내에서 가능한 다음 글자가 하나뿐이라면 그 글자를 버튼 입력 없이 자동으로 입력해 준다! 자세한 작동 과정을 설명하자면 다음과 같다.

모듈이 단어의 첫 번째 글자를 추론하지는 않는다. 즉, 사전의 모든 단어가 같은 알파벳으로 시작하더라도 반드시 첫 글자는 사용자가 버튼을 눌러 입력해야 한다.

길이가 1 이상인 문자열 c1c2...cn이 지금까지 입력되었을 때, 사전 안의 모든 c1c2...cn으로 시작하는 단어가 c1c2...cnc로도 시작하는 글자 c가 존재한다면 모듈은 사용자의 버튼 입력 없이도 자동으로 c를 입력해 준다. 그렇지 않다면 사용자의 입력을 기다린다.

예를 들면, 사전에 “hello”, “hell”, “heaven”, “goodbye” 4개의 단어가 있고 사용자가 “h”를 입력하면 모듈은 자동으로 “e”를 입력해 준다. 사전상의 “h”로 시작하는 단어들은 모두 그 뒤에 “e”가 오기 때문이다. 그러나 단어들 중 “hel”로 시작하는 것도, “hea”로 시작하는 것도 있기 때문에 여기서 모듈은 사용자의 입력을 기다린다. 이어서 사용자가 “l”을 입력하면 모듈은 “l”을 자동으로 입력해 준다. 그러나 여기서 끝나는 단어인 “hell”과 그렇지 않은 단어인 “hello”가 공존하므로 모듈은 다시 입력을 기다린다. 사용자가 “hell”을 입력하기 원한다면 여기서 입력을 멈출 것이고, “hello”를 입력하기 원한다면 직접 “o” 버튼을 눌러서 입력해 줘야 한다. 따라서 “hello”를 입력하려면 사용자는 총 3번 버튼을 눌러야 하고, “hell”, “heaven”은 2번이다. “heaven”의 경우 “he”에서 “a”를 입력하면 바로 뒷부분이 모두 자동으로 입력되기 때문이다. 비슷하게, “goodbye”는 단 한 번만 버튼을 눌러도 입력이 완료될 것이다. “g”를 입력하는 순간 뒤에 오는 글자가 항상 유일하므로 끝까지 자동으로 입력되기 때문이다. 이때 사전에 있는 단어들을 입력하기 위해 버튼을 눌러야 하는 횟수의 평균은 (3 + 2 + 2 + 1)/4 = 2.00이다.

사전이 주어졌을 때, 이 모듈을 사용하면서 이와 같이 각 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하는 프로그램을 작성하시오.

🔍 접근법

Q.5670 휴대폰 자판 문제입니다.

여러가지 영어 단어들이 저장 되어 있습니다. 그리고 원하는 단어를 자동완성을 이용해 이와 같이 각 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하는 문제입니다.

단어의 자동완성, 대표적인 Trie 알고리즘 문제 중 하나입니다.

Trie를 이용해 풀이가 가능합니다.

Trie를 만들어 Trie에 각 단어들을 모두 저장해줍니다.

그 후 원하는 단어를 Trie를 이용해 탐색합니다.

이때 자동완성 기능을 이용하기 위해 주어진 조건이 있습니다.

바로 다음 경우의 수가 한가지이어야만 바로 자동완성이 가능합니다.

다음에 올 수 있는 알파벳 경우의 수가 두가지 이상이라면 반드시 사용자의 입력이 필요합니다.

그리고 또한 이미 어떠한 단어가 완성이 되었을 때 그 뒤로 새로운 알파벳이 이어져 다음 단어를 탐색하기 위해서도

사용자의 입력이 필요합니다.

Trie 탐색에 이를 이용하면 답을 구할 수 있습니다.

                //자식노드 크기가 2이상이면 선택지가 2가지 이상이므로 입력해야한다
                if(thisNode.childNodes.size() >= 2){
                    count++;
                }

                //자식 노드가 하나라면 자동완성이 되지만 만약 이미 문자열이 완성 된 상태라면 다른 문자열을 위해 입력해야한다.
                if(thisNode.childNodes.size() == 1 && thisNode.isLastString){
                    count++;
                }

💻 코드

package problem.string.trie;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main_5670 {

    static int n;
    static Trie trie;
    static String[] word;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input;
        while ( (input = br.readLine()) != null ){
            n = Integer.parseInt(input);
            word = new String[n];
            for(int i=0; i<n; i++){
                word[i] = br.readLine();
            }
            inputTrie();
            solve();
        }
    }

    private static void inputTrie() {
        Arrays.sort(word);
        trie = new Trie();
        for(int i=0; i<n; i++){
            trie.insert(word[i]);
        }
    }

    private static void solve(){
        int count = 0;
        Arrays.sort(word);
        for(int i=0; i<n; i++) {
            int result = trie.contains(word[i]);
            count+=result;
        }
        System.out.println(String.format("%.2f",(double)count/n));
    }

    static class TrieNode {

        public Map<Character, TrieNode> childNodes = new HashMap<>();
        private boolean isLastString;

        public Map<Character, TrieNode> getChildNodes() {
            return this.childNodes;
        }

        public boolean isLastString() {
            return this.isLastString;
        }

        public void setLastString(boolean lastString) {
            this.isLastString = lastString;
        }
    }

    static class Trie {
        private TrieNode rootNode;

        public Trie() {
            rootNode = new TrieNode();
        }

        // 자식 노드 추가
        boolean insert(String str) {
            TrieNode thisNode = this.rootNode;

            for (int i = 0; i < str.length(); i++) {
                char currentString = str.charAt(i);
                if(thisNode.childNodes.get(currentString) == null){
                    thisNode.childNodes.put(currentString,new TrieNode());
                }
                thisNode = thisNode.childNodes.get(currentString);
            }
            thisNode.setLastString(true);
            return true;
        }

        int contains(String str) {
            TrieNode thisNode = this. rootNode;
            int count = 1;
            thisNode = thisNode.childNodes.get(str.charAt(0));
            for (int i = 1; i < str.length(); i++) {
                char currentChar = str.charAt(i);

                //자식노드 크기가 2이상이면 선택지가 2가지 이상이므로 입력해야한다
                if(thisNode.childNodes.size() >= 2){
                    count++;
                }

                //자식 노드가 하나라면 자동완성이 되지만 만약 이미 문자열이 완성 된 상태라면 다른 문자열을 위해 입력해야한다.
                if(thisNode.childNodes.size() == 1 && thisNode.isLastString){
                    count++;
                }

                thisNode = thisNode.childNodes.get(currentChar);
            }
            return count;
        }
    }
}

Written on May 5, 2021