[BOJ] 5052 전화번호 목록 - JAVA

1. 문제

5052번: 전화번호 목록

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

긴급전화: 911
상근: 97 625 999
선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

---

2. 풀이

Set 사용

Main

전화번호를 String배열에 저장한 후, 길이 순으로 오름차순 정렬한다.

정렬한 배열을 check메서드의 파라미터로 넣고 true라면 YES, false라면 NO를 sb에 더한다.

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   int T = Integer.parseInt(in.readLine());
   StringBuilder sb = new StringBuilder();

   int N;
   String[] tell;
   for(int tc=0;tc<T;tc++){
      N = Integer.parseInt(in.readLine());
      tell = new String[N];
      for(int i=0;i<N;i++) tell[i] = in.readLine();
      Arrays.sort(tell, (a,b)->a.length()-b.length());

      if(check(tell)) sb.append("YES\n");
      else sb.append("NO\n");

   }

   System.out.print(sb);
}

check

1.  Set을 하나 생성해서 길이가 짧은 것부터 차례로 더한다. 

2.  더하기 전에 현재 더할 문자열 s를 끝에서부터 하나씩 길이를 줄여가면서 set에 동일한 전화번호가 있는지 확인한다. 

3.  있다면 바로 false를 반환하면서 메서드를 종료한다.

4.  위에서 메서드가 종료되지 않았다면 일관성 있는 전화번호 목록이다. true를 리턴한다.

public static boolean check(String[] tell){
   Set<String> set = new HashSet<>();
   for (String s : tell) {
      for (int len = s.length(); len > 0; len--) {
         if (set.contains(s.substring(0, len))) return false;
      }
      set.add(s);
   }
   return true;
}

 

Trie 사용

Trie 클래스

숫자를 뜻하는 10칸 배열, 마지막 문자열인지 체크하는 isEnd를 저장한다.

static class Trie {
   Trie[] next = new Trie[10];
   boolean isEnd;
   Trie(boolean isEnd){
      this.isEnd = isEnd;
   }
}

Main

위의 set버전과 동일하다.

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   int T = Integer.parseInt(in.readLine());
   StringBuilder sb = new StringBuilder();

   int N;
   String[] tell;
   for(int tc=0;tc<T;tc++){
      N = Integer.parseInt(in.readLine());
      tell = new String[N];
      for(int i=0;i<N;i++) tell[i] = in.readLine();
      Arrays.sort(tell, (a,b)->a.length()-b.length());

      if(check(tell)) sb.append("YES\n");
      else sb.append("NO\n");

   }

   System.out.print(sb);
}

check

1.  head를 하나 만든다.

2.  tell에 있는 전화번호를 하나씩 탐색한다. 만약 node의 next[num]이 null값이라면 새로 생성한다.

3.  문자열 s의 숫자 하나씩 탐색하되, 탐색하는 중간에 node[next]의 isEnd가 true라면 s[0:j]까지의 문자열이 이미 존재하는 것이다. false를 반환한다.

4.  위에서 종료되지 않았다면 일관성 있는 전화번호 목록이다. true를 반환한다.

public static boolean check(String[] tell){
   Trie head = new Trie(false);
   Trie node;
   int num;
   for (String s : tell) {
      node = head;
      for (int j = 0; j < s.length(); j++) {
         num = s.charAt(j) - '0';
         if (node.next[num] == null) node.next[num] = new Trie(j==s.length()-1);
         else if (node.next[num].isEnd) return false;
         node = node.next[num];
      }
   }
   return true;
}

---

3. 결과

아래가 Set, 위의 두개가 Trie다. 문자열을 길이 역순으로 정렬하고 isEnd없이 사용했는데, 길이순으로 정렬하고 isEnd=true인지 파악하는 게 더 빠를 것 같아 변경했다.

시간초과만 나지 않는다면 마음 편하게 set 사용하는 게 더 좋을 것 같다. (구현이 더 편함 ^_^)