[백준(Python/Java)] 5052_전화번호 목록

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

이 문제를 푸는 방법은 크게 두 가지가 있습니다.

 

첫번째는 Trie 자료구조를 이용해서 문자열 탐색을 하는 방법이고, 두번째는 제가 푼 방법처럼 정렬을 이용해 탐색을 하는 방법입니다.

 

조금 더 일반적인 풀이 방법은 Trie 자료구조를 이용하는 것이겠지만 이 문제는 하나의 전화번호가 다른 전화번호의 Prefix가 되는지 여부만 판별해주면 되기 때문에 정렬을 이용할 수 있다고 생각했습니다.

 

즉, 두 문자열이 존재할 때 한 문자열이 다른 문자열의 Prefix라면, 두 문자열은 반드시 사전순으로 정렬했을 때 붙어있어야만 하죠. 이 아이디어를 바탕으로 코드를 구현하면 쉽게 문제를 해결할 수 있습니다.

 

코드는 아래와 같습니다.

 

[풀이 - 파이썬]

import sys
input = sys.stdin.readline

tc = int(input())
for _ in range(tc):
    n = int(input())
    phoneNum = [input().rstrip() for _ in range(n)]

    # 번호가 접두어라면 서로 연속된 위치에 위치한다.
    phoneNum.sort()
    flag = True
    for i in range(len(phoneNum)-1):
        # 다음 번호가 이전 번호로 시작한다면 일관성이 없는 전화번호임
        if phoneNum[i+1].startswith(phoneNum[i]):
            print("NO")
            flag = False
            break
    if flag:
        print("YES")

[풀이 - 자바]

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.sql.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class B_5052 {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        for(int i = 0; i < tc; i++) {
            int n = Integer.parseInt(br.readLine());

            // 전화번호들을 입력받기
            List<String> phoneNum = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                phoneNum.add(br.readLine());
            }

            // 번호를 오름차순 정렬
            Collections.sort(phoneNum);

            boolean flag = true;
            for (int j = 0; j < phoneNum.size() - 1; j++) {
                String pre = phoneNum.get(j);
                String after = phoneNum.get(j + 1);
                if(after.startsWith(pre)){
                    System.out.println("NO");
                    flag = false;
                    break;
                }
            }
            if (flag) {
                System.out.println("YES");
            }
        }
    }
}