자동 완성(트라이) - Level4

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

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

자동완성

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.
효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.

예를 들어, 학습된 단어들이 아래와 같을 때

go gone guild

• go를 찾을 때 go를 모두 입력해야 한다.
• gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신할 수 없다.)
• guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다.

이 경우 총 입력해야 할 문자의 수는 7이다.

라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.

입력 형식

학습과 검색에 사용될 중복 없는 단어 N개가 주어진다.
모든 단어는 알파벳 소문자로 구성되며 단어의 수 N과 단어들의 길이의 총합 L의 범위는 다음과 같다.

• 2 <= N <= 100,000
• 2 <= L <= 1,000,000

출력 형식

단어를 찾을 때 입력해야 할 총 문자수를 리턴한다.

입출력 예제

wordsresult

["go","gone","guild"]	7
["abc","def","ghi","jklm"]	4
["word","war","warrior","world"]	15

입출력 설명

• 첫 번째 예제는 본문 설명과 같다.
• 두 번째 예제에서는 모든 단어들이 공통된 부분이 없으므로, 가장 앞글자만 입력하면 된다.
• 세 번째 예제는 총 15 자를 입력해야 하고 설명은 아래와 같다.
  • word는 word모두 입력해야 한다.
  • war는 war 까지 모두 입력해야 한다.
  • warrior는 warr 까지만 입력하면 된다.
  • world는 worl까지 입력해야 한다. (word와 구분되어야 함을 명심하자)

 

import java.util.*;

class Solution {
    
    static int answer =0;
    class Node{ //노드정의
        int cnt; //해당 문자가 포함이 된 단어가 몇개인지
        Map<Character,Node>children; //자식 노드가 여러개 일수도 있으므로
        
        public Node(){
            children = new HashMap<>(); 
        }

    }
    
    
    public void check(Node curr, String word){ // 어떤 글자부터 cnt가 1개가 되는지 확인을 한다
       
        char[] letters = word.toCharArray(); // 문자열을 문자로 바꿈
        for(int i=0; i<letters.length; i++){ 
            
            curr = curr.children.get(letters[i]); //children 중 letters[i]에 해당하는 문자의 노드를 가져온다
            answer++; // 지나온 문자 만큼 answer값을 더해준다
            if(curr.cnt==1){break;} //만약 cnt 가 1이라면 더이상 문자를 더 탐색하지 않고 끝낸다
            
        }
        
        
    }
    
    public void insert(Node curr, String word){ //각 문자열의 문자들을 노드로 넣어준다.
       
        
       char[] letters = word.toCharArray();
        for(int i=0; i<letters.length; i++){
            
            char c = letters[i];
            curr = curr.children.computeIfAbsent(c,l -> new Node()); // 자식 노드중에 c에 해당하는 문자의 노드를 가져온다 만약없으면 새로 만들어서 가져온다
            curr.cnt++; //가져온 노드의 cnt 값을 증가시켜준다.
            
        }
    }
    
    
    
    public int solution(String[] words) {

        Node root = new Node();
        for(int i=0; i<words.length;i++){
        
            insert(root, words[i]); //words에 있는 문자들을 모두 insert
            
        }
        
        for(int i=0; i<words.length;i++){
        
            check(root, words[i]); // insert 끝난 트리에서 몇번을 탐색하면 모든 글자가 나올 수 있는지 구한다.
            
        }
      return answer;
    }
}