[Programmers] 전화번호 목록 JAVA

반응형

728x90

[Programmers] 전화번호 목록 - LV 2

---

접근

• 완전 탐색
• 해시
• Trie

---

풀이

전화번호가 들어있는 배열이 주어지고 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false 없다면 true를 반환하는 문제이다. [119, 119552]와 같은 번호가 주어졌을 때 119가 다른 번호인 119552의 접두어이기 때문에 false를 반환해야 한다.

---

완전 탐색 

단순하게 하나씩 다 비교해 보는 방법이다. 전화번호를 길이순으로 정렬해 준 뒤 짧은 번호들을 접두어로 보고 긴 번호들에 하나씩 전부 비교해 보는 방법이다. 

    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book, Comparator.comparingInt(String::length));

        for (int i = 0; i < phone_book.length; i++) {
            String pre = phone_book[i];
            for (int j = phone_book.length - 1; j > i; j--) {
                if(phone_book[j].startsWith(pre))
                    return false;
            }
        }

        return true;
    }

정확성 테스트는 100으로 통과했지만 효율성 테스트가 같이 존재하는 문제였다. 효율성 테스트에서 테스트 3, 4번이 시간 초과로 실패했다. 아무래도 전화번호의 길이는 최대 20이지만 배열의 길이는 최대 1,000,000으로 단순 반복으로 해결하기엔 부담이 되었다. 

---

해시

생각해보니 해시 카테고리의 문제였기 때문에 해시를 이용한 자료구조를 사용해 풀면 효율성 테스트에 통과가 될 것이다. HashMap을 사용하기엔 조금 애매한 부분이니 HashSet을 사용해 풀었다.

    public boolean solution(String[] phone_book) {
        Set<String> phoneSet = new HashSet<>(Arrays.asList(phone_book));
        
        for (String phone : phone_book) {
            for (int i = 1; i < phone.length(); i++) {
                String pre = phone.substring(0, i);
                if (phoneSet.contains(pre)) {
                    return false;
                }
            }
        }
        
        return true;
    }

그리고 접두어 비교 방식을 변경했다. 기존 방식은 현재 선택한 번호가 다른 번호의 접두어인지 다른 번호와 비교하는 방법이었는데 그 방법을 그대로 적용한다면 Set을 iterator로 돌려야 하고 그렇게 되면 사실상 완전 탐색과 다를 게 없기 때문에 현재 번호를 한 개씩 잘라 부분 문자열로 만든 뒤 부분 문자열이 Set에 포함되어 있는지 검사하는 방법으로 변경했다. 그렇게 되면 Set에 [119, 119552]라는 번호가 있을 때 현재 번호가 119552라면 1, 11, 119, 1195, 11955, 119552가 Set에 들어있는지 검사하기 때문에 위의 코드와 반대 개념으로 현재 번호의 접두사가 Set 내에 존재하는지 검사하는 것이다. 

//최악의 경우 연산 횟수 비교
배열 길이 = 1,000,000 전화번호 길이 = 20

//완전 탐색
외부 루프 = 0 ~ 999,999
내부 루프 i + 1 ~ 999,999

총 연산 횟수 = (1,000,000 * 999,999) / 2 (등차수열 합 공식) = 499,999,500,000

//해시
전화번호 개수(배열 길이) = 1,000,000
전화번호 길이 = 20
전화번호에 확인하는 접두사 수 = 19

총 연산 횟수 = 1,000,000 * (20 - 1) = 19,000,000

-----------------------------------------------
완전 탐색 = 499,999,500,000
해시 = 19,000,000

두 코드의 최악의 경우 연산 횟수를 비교한 것으로 엄청난 차이가 나는 것을 볼 수 있다.

---

Trie

trie를 사용해도 풀 수 있는 문제이기 때문에 trie를 사용해서도 풀어봤다. 

    private class Trie {
        public Trie[] next;
        public boolean end;

        public Trie() {
            this.next = new Trie[10];
            this.end = false;
        }
    }

옛날에 어디서 풀었던 trie 구조를 떠올리며 간단하게 정의했다. 숫자는 0부터 9까지 10개가 존재하니 next로 길이가 10인 Trie 배열을 선언했다. 그리고 end 포인트로 해당 번호의 끝을 표시한다. 

    public boolean solution(String[] phone_book) {
        Trie root = new Trie();

        for (String s : phone_book) {
            Trie pointer = root;

            for (char c : s.toCharArray()) {
                if (pointer.next[c - '0'] == null) {
                    pointer.next[c - '0'] = new Trie();
                }
                pointer = pointer.next[c - '0'];

                if (pointer.end) {
                    return false;
                }
            }

전화번호를 삽입하는 동시에 접두어를 확인하는 코드이다. 좀 더 자바스럽게 함수로 뽑아내고 할 순 있었지만 코드가 복잡하지 않아서 그냥 내버려두었다. root 노드를 생성하고 pointer를 통해 위치를 이동하며 전화번호를 삽입하게 된다. 값은 root 노드의 다음 노드부터 저장되며 다음 번호가 들어갈 자리가 null이라면 새로 저장하는 번호이기 때문에 새로운 노드를 생성해 주고 이미 존재한다면 다음 번호 저장을 위해 포인터만 옮겨준다. 그리고 만약에 번호 저장 중 현재 노드에 end 포인터가 활성화되어 있다면 해당 노드까지의 전화번호가 존재하는 것이기 때문에 접두어 번호를 찾은 것으로 false를 반환한다. 

	    pointer.end = true;

            for (Trie trie : pointer.next) {
                if (trie != null) {
                    return false;
                }
            }
        }
        
        return true;
    }

번호 저장이 끝나면 end 포인터를 활성화 하고 현재 노드에서 다음 노드들을 검사해 이미 저장된 번호가 있는지 검사한다. 만약 Trie에 123456이라는 번호가 저장되어 있고 방금 저장한 번호가 1234라고 할 때 1234를 123456의 접두어로 쓸 수 있는지 검사하는 방법이 4와 연결된 다음 노드가 있는지 체크하는 것이다. 위의 과정은 전화번호 삽입 후 4에서 연결된 노드가 있는지 확인하는 것이고 연결된 노드가 있다면 방금 삽입한 번호가 접두어로 사용이 가능하다는 뜻이다. 

---

전체 코드

완전 탐색 (효율성 테스트 통과 X)

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book, Comparator.comparingInt(String::length));

        for (int i = 0; i < phone_book.length; i++) {
            String pre = phone_book[i];
            for (int j = phone_book.length - 1; j > i; j--) {
                if(phone_book[j].startsWith(pre))
                    return false;
            }
        }

        return true;
    }
}

 

해시

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Set<String> phoneSet = new HashSet<>(Arrays.asList(phone_book));
        
        for (String phone : phone_book) {
            for (int i = 1; i < phone.length(); i++) {
                String prefix = phone.substring(0, i);
                if (phoneSet.contains(prefix)) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

 

Trie

class Solution {
    private class Trie {
        public Trie[] next;
        public boolean end;

        public Trie() {
            this.next = new Trie[10];
            this.end = false;
        }
    }
    
    public boolean solution(String[] phone_book) {
        Trie root = new Trie();

        for (String s : phone_book) {
            Trie pointer = root;

            for (char c : s.toCharArray()) {
                if (pointer.next[c - '0'] == null) {
                    pointer.next[c - '0'] = new Trie();
                }
                pointer = pointer.next[c - '0'];

                if (pointer.end) {
                    return false;
                }
            }

            pointer.end = true;

            for (Trie trie : pointer.next) {
                if (trie != null) {
                    return false;
                }
            }
        }
        
        return true;
    }
}