프로그래머스 - 자동완성 문제 (자바)

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

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

해당 문제는 문자열 정렬을 통한 풀이와 Trie라는 자료구조를 사용하는 풀이 두가지가 있습니다.

 

1. 정렬

문자열의 사전순으로 정렬하면 근접한 문자와 비교해서 풀면 됩니다.

주의점은

하나의 문자가 다른 문자에 완전히 포함되는 경우와 아닌 경우인데

1. warrior, word 의 경우 w까지 만 동일하기 2문자를 치면 자동완성이 가능하지만

2. war, warrior 이렇게 두 문자의 경우  warrior안에 war가  prefix로 포함되기 때문에 war는 war를 쳐야함

1번의 예는 비교하여 같은 문자 + 1만큼 쳐야하고

2번의 예는 war은 비교하여 같은 문자만큼만 쳐야하고 warrior는 +1 만큼 쳐야한다.

 

import java.util.*;
class Solution {
    public int solution(String[] words) {
        int answer = 0;
        Arrays.sort(words);
        int[] counts = new int[words.length];

        for(int i = 0 ; i < words.length - 1; i++) {
            String pre = words[i];
            String next = words[i+1];
            int len = Math.min(pre.length(), next.length());
            int sameCount = getSameCount(pre, next, len);
            
            // len과 sameCount 같은 경우 긴 문자가 짧은 문자를 prefix로 포함하고 있다는 의미
            if(sameCount == len) {
                counts[i] =  Math.max(counts[i], sameCount);
            }else {
                 counts[i] =  Math.max(counts[i], sameCount + 1);
            }
            counts[i + 1] = Math.max(counts[i + 1], sameCount + 1);
        }

        for(int count : counts) {
            answer += count;
        }
        return answer;
    }

    static int getSameCount(String pre, String next, int len) {
        int count = 0;
        for(int j = 0; j < len; j++) {
            if(pre.charAt(j) != next.charAt(j)) {
                return count;
            }
            count++;
        }
        return count;
    }
}

 

 

2.Trie 방법

 

Trie

• 일반 트리 자료구조 중 하나로, Digital Tree, Radix Tree, Prefix Tree라고도 불린다.
• 텍스트 자동 완성 기능과 같이 문자열을 저장하고 탐색하는데 유용한 자료구조이다.
• 각 노드는 <Key, Value> 맵을 가지고 있다. Key는 하나의 알파벳이 되고, Value는 그 Key에 해당하는 자식 노드가된다.

다음은 DEV, DEAR, PIE, POP, POW라는 단어가 들어있는 Trie 자료구조를 도식화한 것이다. 휴대폰 전화번호부에서 검색을 하거나 사전에서 단어를 찾는 것과 같다.

보다자세한 설명(woovictory.github.io/2020/04/22/Java-Trie/)

 

알파벳 26개를 포함할 수있는 Trie배열을 만들고 문자열마다 Trie를 만들어서 추가하면 됩니다.

class Solution {
  public int solution(String[] words) {
      int answer = 0;
      Trie trie = new Trie();
      for(int i = 0; i < words.length; i++) {
          trie.insert(words[i]);
      }
      for(int i = 0; i < words.length; i++) {
          answer += trie.query(words[i]);
      }
      return answer;
  }
}
class Trie {
    boolean isleafNode = true; // 리프노드 여부
    Trie[] subTrie = new Trie[26]; // 알파벳 26개 포함 하도록 길이 설정

    void insert(String key) {
            int index = 0;
            Trie trie;
            if(this.subTrie[charToNumber(key.charAt(index))] == null) {
                trie = this.subTrie[charToNumber(key.charAt(index))] = new Trie();
            }else {
                trie = this.subTrie[charToNumber(key.charAt(index))];
                // 등록된적 있는 노드 이기 때문에 노드를 하나 더 추가하면서 리프노드가 아니게 됨
                trie.isleafNode = false;
            }
            index++;
        
            // 등록할 문자열을 순회하면서 하위 Trie를 생성 및 갱신
            while(index < key.length()) {
                int next = charToNumber(key.charAt(index));
                if(trie.subTrie[next] == null) {
                    trie.subTrie[next] = new Trie();
                }else {
                    trie.subTrie[next].isleafNode = false;
                }
                trie = trie.subTrie[next];
                index++;
            }
    }
    int query(String key) {
           int sameCharCount = 1, index = 0;
            Trie trie = this.subTrie[charToNumber(key.charAt(index))];
            index++;
            while(index < key.length()) {
                int next = charToNumber(key.charAt(index));
                
                if(trie.isleafNode) break;
                
                sameCharCount++;
                trie = trie.subTrie[next]; 
                index++;
            }
            return sameCharCount;
    }
    int charToNumber(char c) {
        return c - 'a';
    }
}