[JAVA] 백준 - 5052 : 전화번호 목록

문제 링크

5052번: 전화번호 목록

 

 

풀이 )

  트라이라는 자료구조를 공부한 다음에 풀었다.

  트라이는 k진 트리의 구조를 띄고 있고, 접두어를 찾을 때 효율적인 자료구조이다.

 

  root 노드를 시작으로 입력받은 숫자를 한자리씩 노드에 추가한다.

  1번 예제에서는 root를 시작으로 911에 대해서 9를 root의 자식 노드로 추가하고 9의 자식에 1, 1의 자식에 1을 추가한 뒤 마지막 1에서 마지막이라는 것을 표시한다.

  97625999은 현재 root에 9가 있기 때문에 9로 이동하고, 이후에 7이 없기 때문에 노드를 추가한 후 이후에도 같은 방식으로 한다.

  마지막 91125426에 대해서는 root에서 9로 이동한 후 1 1을 따라가면 1에 마지막 표시가 있기 때문에 NO를 출력한다.

 

   root

/

9

|     \

1        7

|          |

1         6

|          |

2         2

|          |

5         5

|          |

4         9

|          |

2         9

|          |

6         9

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());
        while(t-- > 0){
            Node root = new Node();

            boolean flag = false;
            int n = Integer.parseInt(br.readLine());
            while(n-- > 0){
                Node cur = root;
                char[] number = br.readLine().toCharArray();
                if(flag == true)
                    continue;
                for(int i = 0; i < number.length; ++i){
                    char num = number[i];
                    if(i == number.length-1)
                        if(cur.children[num-'0'] != null){
                            flag = true;
                            break;
                        }

                    if(cur.children[num-'0'] == null)
                        cur.children[num-'0'] = new Node();
                    cur = cur.children[num-'0'];

                    if(cur.isLast){
                        flag = true;
                        break;
                    }
                    if(i == number.length-1)
                        cur.isLast = true;
                }
            }
            if(flag)
                sb.append("NO\n");
            else
                sb.append("YES\n");
        }
        System.out.print(sb);
    }

    static class Node{
        Node[] children = new Node[10];
        boolean isLast;

        public Node() {}
    }
}

 

주의 )

  중간에 NO를 출력하기 위해 break를 했을 때 n번 입력받는 while을 탈출해서 런타임에러가 났었다.

  자주하는 실수라 기억해둬야할 것 같다.