Today I Learned

오늘은 어제 정리했던 트라이를 활용하기 위해 관련 문제를 풀어봤다.

전화번호 목록

문제

phone_book 전화번호부에 있는 전화번호 중, 한 번호가 다른 번호의 접두어가 되는 경우가 있는 지 확인하려 한다. 예를들어 전화번호부가 {"123", "456", "12345"} 면 123이 12345의 접두어가 된다. 이렇게 접두어가 있으면 false를, 없으면 true를 반환해라. 단, 같은 번호가 중복인 경우는 없고, 전화번호부는 String 배열로 주어진다.

풀이과정

1. 숫자지만 문자열로 주어지는 전화번호부에서 접두어를 찾는 문제이므로 Trie를 사용한다.

2. 우선 Node 클래스를 만든다. 자식 노드를 담을 Map을 만들고 전화번호의 끝인지 판별하는 플래그 isEnd를 만든다.

3. trie 클래스를 생성한다. 루트노드를 만들고 생성자로 루트노드를 빈 노드로 초기화한다.

4. 삽입 과정에서 isEnd를 통해 접두어인지 판별할 수 있다. 따라서 탐색, 삭제 메서드는 필요없이 삽입 메서드만 만든다.

5. for문으로 전화번호를 char로 한자 한자 넣으면서 해당 노드의 isEnd가 true면 접두어인 상태이니 바로 false를 반환하게 한다.

6. ture가 아니면 computeIfAbsent 메서드를 통해 삽입과정을 마저 진행한다.

7. solution 메서드에서 trie 인스턴스를 만들고 전화번호를 차례대로 넣으면서 false가 나오는 경우가 있으면 그대로 반환하고, 그런 경우가 없으면 true를 반환하면서 끝낸다.

Trouble

• 위와 같이 구현했지만 테스트 케이스 8,9,19번에서 통과가 되지 않았다. 코드 로직상에선 큰 문제가 없어보였기 때문에 여러 테스트 케이스를 실험해 보다가 {"1114", "11"} 처럼 접두어가 되는 번호가 뒤에 나오면 이 방식으로는 해결할 수 없다는 것을 알았다.

• 그래서 짧은 번호를 먼저 삽입하면 되겠다고 생각이 들어 phone_book 배열을 전화번호 길이 기준으로 sort를 진행했다. (a,b) -> a.length() - b.length()로 sort를 진행하면 길이가 짧은 번호부터 오름차순으로 정렬이 된다. sort 후에 원래 코드를 진행하니 모든 케이스가 성공적으로 통과되었다.

Java 코드

import java.util.*;
class Solution {
    static class Node{
        Map<Character, Node> child = new HashMap<>();
        boolean isEnd;
    }
    
    class Trie{
        Node rootNode;
        
        Trie(){
            rootNode = new Node();
        }
        
        boolean insert(String str){
            Node node = this.rootNode;
            
            for(int i=0; i<str.length(); i++){
                if(node.isEnd) return false;
                
                char c = str.charAt(i);
                node = node.child.computeIfAbsent(c,k -> new Node());
            }
            node.isEnd = true;
            return true;
        }
        
    }
    
    public boolean solution(String[] phone_book) {
        Trie trie = new Trie();
        Arrays.sort(phone_book, (a,b) -> a.length() - b.length());
        
        for(String p : phone_book){
            boolean flag = trie.insert(p);
            if (!flag) return false;
        }
        return true;
    }
}