[백준] 5052 : 전화번호 목록

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

 

[풀이과정]

N이 10,000이어서 문자의 길이를 오름차순으로 정렬 후 비교해줬다.
처음엔 StringBuilder를 사용하고 subString, equals 메서드를 사용해서 비교를 해줬는데 시간초과가 났다.

그래서 고려한 부분은

 

1. 정렬 기준

길이가 아닌 사전순으로 정렬을 했다. 예로 ["123", "1234", "234"] 이렇게 정렬이 되기 때문에, 앞 뒤의 두 문자열만 비교해주면 쉽게 정답을 알 수 있다.

-> Arrays.sort는 O(N logN)의 시간복잡도

-> 2개씩 비교하므로 총 N-1의 비교 횟수를 가져서 O(N)의 시간복잡도

 

2. 접두어 확인 로직

String의 startsWith메서드를 사용해서 복잡성을 완화했다.

 

그래서 O(N^2)에서 O(N logN)의 시간복잡도로 문제 해결.

 

[정답 코드]

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

/*
전화번호 목록이 일관성이 있는지 없는지 구하기.
일관성 : 한 번호가 다른 번호의 접두어인 경우가 없어야 함.
 */
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static int N;
    static String[] numbers;
    public static void main(String[] args) throws IOException{
        int T = Integer.parseInt(br.readLine());
        for(int t = 0; t < T; t++){
            init();
            if(!isConsist()){
                sb.append("NO\n");
            }
            else{
                sb.append("YES\n");
            }
        }
        /*
        [출력]
        일관성 있으면 YES, 없으면 NO 출력
         */
        System.out.println(sb);
    }

    static void init() throws IOException{
        /*
        [입력]
        1. 테스트 케이스 개수 t (1 <= t <= 50)
        2. 전화 번호 수 n (1 <= n <= 10,000)
        3~n. 전화번호 정보 (길이 : 최대 10, 같은 경우 없음)
         */
        N = Integer.parseInt(br.readLine());
        numbers = new String[N];

        for(int n = 0; n < N; n++){
            numbers[n] = br.readLine();
        }

        //사전순으로 정렬
        Arrays.sort(numbers);
    }

    static boolean isConsist(){
        for(int n = 0; n < N-1; n++){
            if(numbers[n + 1].startsWith(numbers[n])){
                //일관성 없음
                return false;
            }
        }
        //일관성 있음
        return true;
    }
}

 

[시간 초과 코드]

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

/*
전화번호 목록이 일관성이 있는지 없는지 구하기.
일관성 : 한 번호가 다른 번호의 접두어인 경우가 없어야 함.
 */
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static int N;
    static StringBuilder[] numbers;
    public static void main(String[] args) throws IOException{
        int T = Integer.parseInt(br.readLine());
        for(int t = 0; t < T; t++){
            init();
            boolean consist = true;
            for(int n = 0; n < N; n++){
                //일관성 없으면
                if(!isConsist(n)){
                    consist = false;
                    break;
                }
            }
            if(consist){
                sb.append("YES" + '\n');
            }
            else{
                sb.append("NO" + '\n');
            }
        }
        /*
        [출력]
        일관성 있으면 YES, 없으면 NO 출력
         */
        System.out.println(sb);
    }

    static void init() throws IOException{
        /*
        [입력]
        1. 테스트 케이스 개수 t (1 <= t <= 50)
        2. 전화 번호 수 n (1 <= n <= 10,000)
        3~n. 전화번호 정보 (길이 : 최대 10, 같은 경우 없음)
         */
        N = Integer.parseInt(br.readLine());
        numbers = new StringBuilder[N];

        for(int n = 0; n < N; n++){
            StringBuilder number = new StringBuilder(br.readLine());
            numbers[n] = number;
        }

        //길이 순으로 정렬
        Arrays.sort(numbers, (a, b) -> a.length() - b.length());
    }

    static boolean isConsist(int start){
        StringBuilder nowNumber = numbers[start];
        int length = nowNumber.length();
        for(int n = start + 1; n < N; n++){
            StringBuilder compareNumber = numbers[n];
            //비교 대상이 더 짧으면 넘기기
            if(compareNumber.length() < length){
                continue;
            }
            //
            if(compareNumber.substring(0, length).equals(nowNumber.toString())){
                //일관성 없음
                return false;
            }
        }
        //일관성 있음
        return true;
    }
}