[백준] 5052번. 전화번호 목록(JAVA)

문제

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

---

풀이(19분)

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {

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

        int t = Integer.parseInt(br.readLine());
        loop1:
        while(t-- > 0){
            int n = Integer.parseInt(br.readLine());
            String[] arr = new String[n];
            for(int i = 0; i < n; i++){
                arr[i] = br.readLine();
            }
            Arrays.sort(arr, (o1, o2) -> {
                return o1.length() - o2.length();
            });
            int maxLength = 0;
            Set<String> sets = new HashSet<>();
            sets.add(arr[0]);
            maxLength = arr[0].length();

            for(int i = 1; i < n; i++){
                for(int j = 1; j <= maxLength; j++){
                    if(sets.contains(arr[i].substring(0,j))){
                        System.out.println("NO");
                        continue loop1;
                    }
                }
                sets.add(arr[i]);
                maxLength = arr[i].length();
            }
            System.out.println("YES");
        }
    }
}

---

문제 풀이 전략

 

문제를 보자마자 트라이 자료구조를 떠올렸으나 시간 복잡도를 계산해보면 굳이 트라이까지 도입할 필요는 없었다.

 

주어진 전화번호를 길이에 따라 정렬하고, 동일한 접두어를 갖는 것이 있는지만 집합을 통해 확인하면 됐다.

중요한 부분은 전화번호를 숫자열이 아닌 문자열으로 처리한 것인데 000212 같은 번호도 있을 수 있기 때문이다!!