프로그래머스 <2018 KAKAO BLIND RECRUITMENT> - 자동완성

Trie와 관련된 문제를 찾던 중에 카카오 블라인드 문제를 접하게되었다.

이번 내 부캠에서 본 코테에 대하여 멤버들과 이야기를 해봤는데 String startwith등 내장 메서드를 이용하셨다고 하셨다.

공부를 하면할 수록 점점 더 처음으로 돌아가는 것 같다...!! 흐흐 궁굼해서 다른 분의 코테를 참고하였다!

 

https://wellbell.tistory.com/166

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

 

첫 번째 방법은 문자열의 사전 순으로 정렬하면 근접한 문자와 비교해서 풀면 된다고 하신다.

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;
    }
}

 

 

---

 

두 번째 방법인 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';
    }
}