[백준 5052] 전화번호 목록

문제 링크: https://www.acmicpc.net/problem/5052

---

풀이

정렬과 트리를 이용하여 풀 수 있는 문제였다. 풀이를 찾아보니 훨씬 센스있는 방법으로 푼 분들도 많았다.

 

(1) 전화번호 정렬하기

N = Integer.parseInt(br.readLine());
String[] phoneNumbers = new String[N];
for (int i=0; i<N; i++) {
    phoneNumbers[i] = br.readLine();
}
Arrays.sort(phoneNumbers);

 

길이가 짧은 문자열이 앞에 와야 하기 때문에 입력받은 전화번호를 정렬해주었다. 911과 91125426이 있으면, 911을 먼저 체크해야 91125426이 911을 포함하고 있다는 것을 알 수 있기 때문이다.

 

(2) 트리 구성하기

접두어 검사는 결국 각 문자를 비교해가며 이전에 여기서 끝난 문자열이 있었는지를 체크해야 한다.

그러자 트리가 생각났고, 아래와 같은 아이디어를 얻을 수 있었다.

 

가장 먼저 911을 트리에 넣어둔 상태다. cnt는 해당 노드에서 끝나는 문자열의 개수이다.

이 상태에서 91125426을 체크한다고 생각해보자.

 

가장 먼저 첫번째 문자 9이다. cnt==0이므로 입력받은 전화번호 중에 9는 없다는 사실을 알 수 있다.

 

그 다음은 두번째 문자 1이다. 여전히 cnt==0이므로 입력받은 전화번호 중에 91이 없다는 사실을 알 수 있다.

 

세 번째 문자 1을 검사하면, cnt==1이다. 이전에 입력받은 문자열 중 911이 있다는 의미다.

따라서 이 전화번호부는 일관성 있는 전화번호부가 아니므로, NO를 출력하고 다음 테스트케이스로 넘어간다.

 

대략적인 밑그림을 그렸으니, 코드로 구현하기만 하면 된다.
먼저 노드 객체에 넣을 필드값을 생각해보았다.

• cnt: int형. 현재 노드에서 끝나는 문자열이 있는지를 의미
• Node[] child: 크기 10짜리 Node형 배열. 배열의 인덱스는 다음에 오는 문자를 의미한다.

(지금보니 cnt대신 isEnd라는 이름의 boolean형 필드로 두는게 더 나은 것 같다.)

1. 현재 노드의 cnt값이 양수이면 이전에 여기서 끝난 문자열이 있다는 의미
-> NO를 출력하고 다음 테스트케이스로 넘어감

2. 다음 문자를 검사. 다음 문자가 n이면 다음 노드는 child[n]이 됨
3. 만약 child[n]이 null면 새 인스턴스 할당해주기
4. 다음 노드로 이동
5. 다음 문자가 없다면, 현재 노드의 cnt를 1 증가시키기

 

위와 같은 알고리즘을 코드로 옮기면 이렇게 된다.

 

boolean result = true;
for (int i=0; i<N; i++) {
    result = isConsistentPhoneNumber(phoneNumbers[i]);
    if(!result) break;
}

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

 

static boolean isConsistentPhoneNumber(String numbers) {
    Node now = root;
    for (int i=0; i<numbers.length(); i++) {
        if(now.cnt!=0) return false;
        int n = numbers.charAt(i) - '0';
        if(now.child[n]==null) {
            now.child[n] = new Node();
        }
        now = now.child[n];
    }
    now.cnt++;
    return true;
}

 

메서드만 종료하는게 아니라 N개의 전화번호부를 검사하는 반복문까지 함께 탈출해야 한다.

반복문이 끝나면 결과에 따라 YES나 NO를 출력해야 하기 때문에 메서드가 boolean값을 반환하도록 설계했다.

---

전체 코드

 

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

class Node {
    int cnt;
    Node[] child;
    public Node() {
        this.cnt = 0;
        this.child = new Node[10];
    }
}

public class Main_5052_전화번호목록 {
    static int T, N;
    static Node root;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        T = Integer.parseInt(br.readLine());
        while(T>0) {
            root = new Node();
            N = Integer.parseInt(br.readLine());
            String[] phoneNumbers = new String[N];
            for (int i=0; i<N; i++) {
                phoneNumbers[i] = br.readLine();
            }
            Arrays.sort(phoneNumbers);
            boolean result = true;
            for (int i=0; i<N; i++) {
                result = isConsistentPhoneNumber(phoneNumbers[i]);
                if(!result) break;
            }

            if(result) sb.append("YES\n");
            else sb.append("NO\n");
            T--;
        }
        System.out.println(sb.toString());
    }

    static boolean isConsistentPhoneNumber(String numbers) {
        Node now = root;
        for (int i=0; i<numbers.length(); i++) {
            if(now.cnt!=0) return false;
            int n = numbers.charAt(i) - '0';
            if(now.child[n]==null) {
                now.child[n] = new Node();
            }
            now = now.child[n];
        }
        now.cnt++;
        return true;
    }
}