[programmers/kakao] [3차] 자동완성 (Java)

문제

출처 : https://programmers.co.kr/learn/courses/30/lessons/17685?language=java 

코딩테스트 연습 - [3차] 자동완성

검색어 자동완성 기능을 만들고, 모든 문자를 찾기위해서 최소 몇번 타이핑해야하는지 찾는 문제다.

---

풀이

전형적인 Trie 문제였다 모든 단어의 길이를 합쳤을때 최대 1,000,000길이가 나오니 Trie 구조를 만드는데, 1,000,000번 반복하며, 모든 단어의 길이의 합이 최대 1,000,000 이므로 모든 단어를 찾기위해서 최악의 경우 1,000,000번 반복한다. 따라서, Trie구조를 사용하면, 최대 2,000,000번 반복으로 답을 구할수있다. (따라서, 시간복잡도는 O(2L)이다.)

 

기본적인 Trie구조에 최종적으로 도달할 수 있는 단어의 갯수를 저장시켜주면 된다. 그리고, 단어마다 최종적으로 도달할 수 있는 단어의 갯수가 1일때까지 Trie구조를 탐색시켜준다.

 

Trie 구조 소스코드

    private static class Trie{
       
        private final char alphabet;
        private int candidateWordCount;
        private Trie[] connectedTrie;
       
        public void connectTrie(Trie trie){
            this.connectedTrie[(int)trie.getAlphabet()-(int)'a'] = trie;
        }
       
        public char getAlphabet(){
            return this.alphabet;
        }
       
        public void plusCandidateWordCount(){
            this.candidateWordCount++;
        }
       
        public boolean isOneCandidate(){
            return this.candidateWordCount == 1 ? true : false;
        }
        
        public Trie getConnectedTrie(char alphabet){
            return this.connectedTrie[(int)alphabet-(int)'a'];
        }
       
        public Trie(char alphabet){
            this.alphabet = alphabet;
            this.connectedTrie = new Trie[26];
            this.candidateWordCount = 1;
        }
       
    }

 

Trie 구조 만드는 소스코드

    private Trie makeTrie(String[] words){
        Trie rootTrie = new Trie('0');
        rootTrie.plusCandidateWordCount();
        for(int i = 0; i < words.length; i++){
            String word = words[i];
            Trie trieChain = rootTrie;
            for(int j = 0; j < word.length(); j++){
                char alphabet = word.charAt(j);
                Trie trie = trieChain.getConnectedTrie(alphabet);
                if(this.isNull(trie)) trieChain.connectTrie(new Trie(alphabet));
                else trie.plusCandidateWordCount();
                trieChain = trieChain.getConnectedTrie(alphabet);
            }
        }
        return rootTrie;
    }    
   
    private boolean isNull(Object obj){
        return obj == null ? true : false;
    }

(만들어진 Trie구조는 시작점 rootTrie를 바탕으로 연결된다.)

 

Trie구조를 바탕으로 타이핑횟수를 계산하는 소스코드

    private int calcTypingCount(String[] words, Trie rootTrie){
        int typeCount = 0;
        for(int i = 0; i < words.length; i++){
            String word = words[i];
            Trie trieChain = rootTrie;
            for(int j = 0; j < word.length(); j++){
                if(trieChain.isOneCandidate()) break;
                trieChain = trieChain.getConnectedTrie(word.charAt(j));
                typeCount++;
            }
        }
        return typeCount;
    }

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/%5Bprogrammers%5D%20%5B3%EC%B0%A8%5D%20%EC%9E%90%EB%8F%99%EC%99%84%EC%84%B1/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃