ShinJongPark | Sean P
  • Jan 25, 2021

[프로그래머스] Level4 - 자동완성 2018 카카오 문제

 
by 박신종

> 문제

문제 : [자동완성 2018 카카오 문제]



> 문제풀이

Trie 자료구조를 구현하여 풀이하였다.

입력해야 할 문자의 수는 dfs로 탐색하였으며,

cnt가 1이거나 마지막 문장인 경우(lastChar==true)의 depth를 결과값에 더해가며 풀이하였다.

cnt가 1인경우는 문장이 하나밖에 없기 때문에 더이상 탐색할 필요가 없으며,

마지막 문장인 경우(lastChar==true)에는 이어서 문장이 더 있을 수 있기 때문에 더 탐색한다.

소스는 다음과 같다.


import java.util.*;
class Solution {
    static class Trie{
        private Node root;
        public Trie(){
            this.root = new Node();
        }
        public void append(String word){
            Node node = this.root;
            char c = ' ';
            for(int i=0; i<word.length(); i++){
                c = word.charAt(i);
                if(node.child.get(c) == null){
                    node.child.put(c, new Node());
                }
                node = node.child.get(c);
                node.cnt++;
                if(i==word.length()-1) node.lastChar = true;
            }
        }
        
        static int res;
        public int calLengthStr(){
            dfs(0, this.root);
            return res;
        }
        public void dfs(int depth, Node node){
            if(node.cnt == 1){
                res += depth;
                return;
            }
            if(node.lastChar == true) {
                res += depth;
            }
            Iterator<Character> it = node.child.keySet().iterator();
            while(it.hasNext()){
                char c = it.next();
                dfs(depth+1, node.child.get(c));
            }
        }
        static class Node{
            int cnt;
            Map<Character, Node> child;
            boolean lastChar;
            
            public Node(){
                this.child = new HashMap<>();
            }
        }
        
    }
    
    public int solution(String[] words) {
        Trie trie = new Trie();
        for(int i=0; i<words.length; i++){
            trie.append(words[i]);
        }
        int answer = trie.calLengthStr();
        return answer;
    }
}




문제 출처 : Programmers




Search