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

문제 설명

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

문제 풀이

• Trie를 이용한 트리 자료구조로 풀이하였다.
• 풀이는 다음과 같다.

  1. 기본 Trie를 변형하여 각 노드가 이전 노드를 기억하는 Trie에 모든 문자열 insert
  2. 각 문자열에 대해 아래와 같이 최소 입력 횟수 계산
     0. 트리를 순회하여 해당 단어의 끝 노드로 이동
     1. 끝 노드가 leaf노드가 아니면 -> 무조건 문자열 길이만큼 입력 필요
     2. 끝 노드가 leaf노드이면 -> 하나씩 이전 노드로 옮겨가며 다음 확인
     - 노드가 끝노드이거나 노드 자식이 2개 이상이면 멈춤
- 해당 노드 다음 노드까지 입력 필요

소스 코드 (JAVA)

import java.util.HashMap;
import java.util.Map;

class Solution {

    public class Node {
        Map<Character, Node> child = new HashMap<>();
        Node before = null;
        Boolean isEnd = false;
    }

    public class Trie {
        public Node root = new Node();

        public void insert(String input) {
            Node node = this.root;

            for (int i = 0; i < input.length(); i++) {
                Node before = node;
                node = node.child.computeIfAbsent(input.charAt(i), k -> new Node());
                node.before = before;
            }

            node.isEnd = true;
        }

        //각 단어의 최소 입력 횟수 계산
        public int calInputCnt(String input) {
            Node node = this.root;

            //마지막 노드로 이동
            for (int i = 0; i < input.length(); i++) {
                node = node.child.getOrDefault(input.charAt(i), null);
            }

            //1. 마지막 노드가 leaf 노드가 아닐 경우
            if (node.child.size() != 0) return input.length();

            //2. 마지막 노드가 leaf 노드일 경우
            int cnt = 0;
            while(true) {
                node = node.before;
                if (node == null) {
                    cnt--;
                    break;
                }
                if (node.isEnd == false && node.child.size() == 1)
                    cnt++;
                else
                    break;
            }
            return input.length() - cnt;
        }
    }

    public int solution(String[] words) {
        Trie trie = new Trie();
        //트라이 입력
        for (int i = 0; i < words.length; i++)
            trie.insert(words[i]);

        //각 단어의 최소 입력 횟수 계산
        int result = 0;
        for (int i = 0; i < words.length; i++) {
            result += trie.calInputCnt(words[i]);
        }
        return result;
    }
}