백준 5052번 전화번호 목록 :: 마이구미

이 글은 백준 알고리즘 문제 5052번 "전화번호 목록" 을 풀이한다.

해싱, 트리와 같은 자료구조를 통해 해결할 수 있다.

본인은 논리적 사고를 통한 센스로 문제를 쉽게 풀이하는 것을 다뤄본다.

5052번 "전화번호 목록" - https://www.acmicpc.net/problem/5052

전화번호 목록이 주어진다. 이 때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

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

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

문제를 이해함에 있어, 중요한 것은 긴급전화가 가장 첫줄 온다는 것으로 이해하면 안된다.

다음과 같이 주어질 수도 있다.

91125426
95625999
911

즉, 모든 전화번호 목록에 대해 일관성을 유지해야하는 것이다.

단순하게 일일이 비교하기에는 시간 초과를 초래하게 된다.

그렇기에, 주어진 입력의 정수가 아닌 문자열을 기준으로 오름차순 결과는 다음과 같다.

// 정렬 전
134
15
12
134
1234

// 정렬 후
12
1234
13
134
15

위와 같이 정렬 된 문자열들을 보면, 규칙이 보이게 된다.

인덱스 i는 다음 인덱스 i + 1에 대해 포함되었는지만 판단하면 문제를 해결할 수 있다.

그 과정에서 두 문자열의 길이가 같다면 비교할 필요가 없으니 조건을 부여할 수 있다.

비교할 필요가 없는 이유는 문제에서 같은 번호는 주어지지 않는다고 명시하고 있다.

private void solve() {
    int t = sc.nextInt();
    StringBuilder sb = new StringBuilder();
 
    while (t-- > 0) {
        int n = sc.nextInt();
        String[] array = new String[n];
        boolean flag = true;
 
        for (int i = 0; i < n; i++) {
            array[i] = sc.readLine();
        }
 
        Arrays.sort(array);
 
        for (int i = 0; i < n - 1; i++) {
            int current = array[i].length();
            int next = array[i + 1].length();
 
            if (current < next) {
                if (array[i + 1].indexOf(array[i]) > -1) {
                    flag = false;
                    break;
                }
            }
        }
 
        if (flag) {
            sb.append("YES\n");
        } else {
            sb.append("NO\n");
        }
 
    }
    System.out.println(sb.toString());
}