[프로그래머스] 자동완성

문제

programmers.co.kr/learn/courses/30/lessons/17685

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

문제해결방법

이 문제는 Trie 자료구조에 해당 문자열들을 저장해서 풀었다.

Trie에 문자열을 저장할 때 다음 문자를 저장하면서 그 문자까지 온 문장의 개수를 세서 기록해두었고

각 문자열을 탐색하면서 해당 문자에 도착했을때 1이 기록되어 있으면 문자열을 특정지을 수 있으므로

그 수를 합산해서 계산해주었다.

코드

package Programmers;
 
class TrieNode {
    int count;
    TrieNode[] next;
    TrieNode() {
        this.count = 0;
        next = new TrieNode[26];
    }
}
 
class Trie {
    TrieNode root;
    Trie() {
        root = new TrieNode();
    }
    
    void addTrie(String str) {
        TrieNode cur = root;
        for(int i=0; i<str.length(); i++) {
            int index = str.charAt(i) - 'a';
            if(cur.next[index] == null) cur.next[index] = new TrieNode();
            cur = cur.next[index];
            cur.count++; 
        }
    }
    
    int getTrie(String str) {
        TrieNode cur = root;
        for(int i=0; i<str.length(); i++) {
            int index = str.charAt(i) - 'a';
            cur = cur.next[index];
            if(cur.count==1) return i+1; 
        }
        return str.length();
    }
}
 
class Solution_자동완성 {
    public static int solution(String[] words) {
        int answer = 0;
        Trie trie = new Trie();
        for(int i=0; i<words.length; i++) trie.addTrie(words[i]);
        for(int i=0; i<words.length; i++) answer += trie.getTrie(words[i]);
        return answer;
    }
    
    public static void main(String[] args) {
        String[] words = {"word","war","warrior","world"};
        System.out.println(solution(words));
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.