[프로그래머스] 전화번호 목록 (JAVA/자바)

흶·2021년 9월 16일

알고리즘 프로그래머스

Algorithm

목록 보기

56/60

문제 링크

풀이

해시 카테고리로 분류되어있는 문제이긴 한데, Trie(트라이) 개념을 적용해서 풀이했다.

Trie란?
탐색 트리의 일종으로, 문자열을 빠르게 탐색하게 해주는 자료구조 이다.
즉, '문자열'을 관리하는 방법 중의 하나이다.

문제의 예제1를 그림으로 그리면 아래와 같다. 파란색 노드는 마지막 문자임을 나타낸다.

119를 넣은 뒤 1195524421를 넣으면, 1195524421가 119의 맨 마지막 노드를 포함한다는 것을 알 수 있다! 이런 경우가 생기면 접두어가 존재한다는 것으로 볼 수 있다.

트라이 구현은 정석대로 하진 않았고, Node class를 정의해 그래프를 그리듯이 adj에 하위 노드를 추가하는 방식으로 구현했다.

루트 노드부터 시작하여, 문자열의 문자 하나하나를 보며 자식 노드를 찾거나 새로 생성한다.

처음의 현재 노드(now) = root
now 노드의 자식 노드가 하나도 없으면 자식노드를 하나 새로 생성하고 now를 새로운 노드로 바꿔준다.
now 노드의 자식 노드 중에 지금 찾는 숫자 값을 가진 노드(leaf1)가 있으면
- 어떤 문자열의 끝인지 확인해서
  - 끝 노드가 아니면 now를 해당 자식 노드(leaf1)로 바꿔준다.
  - 끝 노드라면 접두어가 존재하므로 false를 리턴한다.
- 지금 찾는 문자가 없으면 자식 노드를 하나 생성하고 now를 새로운 노드로 바꿔준다.

처리하는 데에 용이하게 하기 위해 문자열의 문자 하나하나를 볼때 굳이 숫자로 parse하여 처리하지 않았다. (char형태로 사용)

코드

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    static class Node{
        char num;		// 노드가 가지는 값
        ArrayList<Node> adj; 	// 자식 노드들의 list
        boolean is_end;		// 현재 노드가 한 문자열의 끝인지 여부

        public Node(char num) {
            this.num = num;
            this.adj = new ArrayList<>();
            this.is_end = false;
        }
    }

public static boolean solution(String[] phone_book) {
        
        // 문자열의 길이 순서대로 오름차순 정렬
        Arrays.sort(phone_book, (s1, s2)->s1.length()-s2.length());
        // Arrays.sort(phone_book, (s1, s2)->s1.compareTo(s2));  // 이렇게 해도 가능

        Node root = new Node('r'); // 루트 노드 생성

        for (int i = 0; i < phone_book.length; i++) {
            String s = phone_book[i];

            Node now = root; // 루트부터 탐색

            OuterLoop:
            for (int j = 0; j < s.length(); j++) {
                char c = s.charAt(j);

                // 현재 노드의 자식 노드가 하나도 없으면 
                // 바로 새로운 노드를 생성하여 자식 노드로 이어주고
                // now(현재 노드)를 방금 생성한 자식 노드로 바꿔준다.
                if (now.adj.size()==0) {
                    Node new_node = new Node(c);
                    now.adj.add(new_node);
                    now = new_node;

                    if (j == s.length() - 1) { // j번째 문자가 마지막 문자라면
                        now.is_end = true; 
                    }
                    continue;
                }


                // 현재 노드(now)의 자식 노드를 하나씩 확인
                for (Node n : now.adj) {
                    if (n.num == c) {
                        if(n.is_end){ 	// 접두사가 있으면 바로 결과 리턴 (false)
                            return false;
                        }else{
                            now = n;	// 현재 노드(now)를 자식노드로 바꿔주고 다시 탐색
                            continue OuterLoop;
                        }
                    }
                }

                // 현재 숫자 값을 가진 노드가 없으면 새로 생성한다.
                Node new_node = new Node(c);
                now.adj.add(new_node);
                now = new_node;

                if (j == s.length() - 1) {
                    now.is_end = true;
                }

            }
        }

        return true;
    }
}