[프로그래머스, 17685] [3차] 자동완성 (java)

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

프로그래머스

728x90

---

메모리: 302 MB, 시간: 233.63 ms

사용 알고리즘: 트리

 

각 단어의 문자들을 하나의 노드로 트리 형태로 만든다.

단어 "go"를 만들기 위해서 root -> 'g' -> 'o' 형태로 트리를 만든다.

단어 "gone"을 만들기 위해서 "go"를 만들며 이미 생성된 노드를 타고 root -> 'g' -> 'o'까지 이동한다.

이어서 이동하며 'o' -> 'n' -> 'e'를 만든다.

마찬가지로 "guild"를 만들기 위해 root -> 'g'까지 이동 후 이어서 'g' -> 'u' -> 'i' -> 'l' -> 'd'까지 만든다.

 

트리 형태로 만들며, 현재 자신의 노드에 몇 개의 단어들이 연결되어 있는지 길이를 저장한다.

만약 길이가 1인 노드라면, 현재 노드까지 단어를 입력했을 때 나올 수있는연결되어 있는 단어가 1개라는 뜻이므로 나머지 단어는 입력하지 않아도 자동 완성 된다는 뜻이다.

import java.util.*;

class Solution {
    
    static class Node {
        private int length; // 자식 노드의 개수
        private Map<Character, Node> child; // 자식 노드
        
        Node() {
            length = 0;
            child = new HashMap<>();
        }
        
        Node add(char c) {
            length++;
            
            Node ret = child.get(c);
            
            if(ret == null) {
                child.put(c, new Node());
                ret = child.get(c);
            }
            
            return ret;
        }
        
        void end() { // 현재 노드에서 끝나는 단어가 있다고 알려주기
            length++;
        }
        
        int size() {
            return length;
        }
        
        Node get(char c) {
            return child.get(c);
        }
    }
    
    public int solution(String[] words) {
        
        // 각 문자들을 Node 객체를 활용하여 트리와 같은 형태로 나타낸다
        Node root = new Node();
        
        char[] arr;
        Node now;
        for(int i = 0; i < words.length; i++) {
            arr = words[i].toCharArray(); // 문자열을 char 배열로 변환
            now = root; // 루트부터 시작
            
            for(int j = 0; j < arr.length; j++) { // 차례로 트리 형태로 만듦
                now = now.add(arr[j]);
            }
            now.end(); // 단어가 끝났다고 알려주기
        }
        
        // 검색 시작
        int answer = 0;
        int length;
        for(int i = 0; i < words.length; i++) {
            arr = words[i].toCharArray(); // 문자열을 char 배열로 변환
            now = root; // 루트부터 시작
            
            // 모든 단어 다 입력한 경우
            answer += arr.length;
            
            for(int j = 0; j < arr.length; j++) {
                now = now.get(arr[j]); // 문자 하나 검색
                length = now.size(); // 현재 문자까지 같은 단어 개수
                
                if(length == 1) { // j번째 문자까지 검색했을 때, 자동 완성 가능
                    answer -= (arr.length - 1) - j; // 입력하지 않은 길이 답에서 빼주기
                    break;
                }
            }
        }
        
        return answer;
    }
}