프로그래머스-전화번호 목록

https://programmers.co.kr/learn/courses/30/lessons/42577

문자열 배열에서 한 문자열이 다른 문자열의 prefix인 경우가 있는지 확인하는 문제이다.

1. 정렬하면 123은 1234 바로 전에 있을 것이므로 인접한 문자열끼리만 prefix인지 보면 된다. 정렬은 O(nlogn) startsWith는 문자열 최대길이가 20으로 상수이므로 무시.

public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        for (int i=0; i<phone_book.length-1; ++i) {
            if (phone_book[i+1].startsWith(phone_book[i]))
                return false;
        }
        return true;
    }

2. 사실 이 문제는 해시카테고리다. 모든 문자열을 Set에 넣은 후에 각 문자열마다 모든 substring들이 Set에 있는지 보면 된다. 정렬없고 Set 연산은 상수라고 보면 Time : O(n). Space도 O(n) 실제로 효율성테스트케이스에서 1번보다 훨씬 빨랐다.

public boolean solution1(String[] phone_book) {
        HashSet<String> set = new HashSet<String>(Arrays.asList(phone_book));
        for (String num : phone_book) {
            for (int i=1; i<num.length(); ++i) {
                String sub = num.substring(0, i);
                if (set.contains(sub))
                    return false;
            }
        }
        return true;
    }

3. prefix/suffix 문제는 Trie로 푸는게 구현은 복잡해도 제일 효율적이다. 나도 Trie를 직접 구현해본 적은 없었는데 이 문제는 다 숫자이므로 Node가 next 10개만 있으면 간단하게 될 것 같아서 해봤다.

• 예를 들어 "123"이 들어오면 root.next[1].next[2].next[3].next = null
• 그다음 문자열이 "12"라면 root.next[1].next[2]가 non-null이고 2가 마지막 글자이므로 12가 기존 123의 prefix.
• 그다음 문자열이 "1234"라면 root.next[1].next[2].next[3]가 non-null이고 leaf node이므로 1234의 prefix인 123이 존재.
• 그러므로 prefix인게 먼저 오든 늦게 오든 찾을 수 있다.
• Time도 O(n). Space는 10^depth(=문자열최대길이)이므로 n과 무관하다. 실제로 겹치는 부분들이 있는걸 생각하면 훨씬 적을듯. 실행결과는 물론 이게 제일 빠르다.

    private static class Node {
        Node[] next;
        Node(boolean isLeaf) {
            next = isLeaf ? null : new Node[10];
        }
        Node add(int c, boolean isLeaf) {
            if (next[c] == null) {
                next[c] = new Node(isLeaf);
                return next[c];
            } else {
                // added "12" and add "1"
                if (isLeaf)
                    return null;
                // added "12" and add "12..."
                else if (next[c].next == null)
                    return null;
                else
                    return next[c];
            }
        }
    }    
    public boolean solution(String[] phone_book) {
        Node root = new Node(false);
        for (String num : phone_book) {
            Node cur = root;
            for (int i=0; i<num.length(); ++i) {
                cur = cur.add(num.charAt(i) - '0', i==num.length()-1);
                if (cur == null)
                    return false;
            }
        }
        return true;
    }