문제링크

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

구현방법

• 일관성이 있는지 없는지 구하는 프로그램

  • 일관성을 유지하는 방법은 한 번호가 다른 번호의 접두인 경우가 없어야한다.

번호 길이순으로 먼저 정렬을 진행.

테스트케이스는 최대 50개

전화번호의 수는 10000개

포함 여부를 확인

• 누적해서 확인 필요.

곰곰히 생각해보니 자바에서 접두어를 확인하는 함수가 존재한다는 걸 생각해냈다.

startWith 함수를 이용한 확인방법

먼저 정렬을 통해서 길이가 작은 순부터 확인 진행

• 길이가 들쑥날쑥 인거보다는 길이 정렬을 통해서 비교도 편하게된다.

• 정렬을 통해서 사전순정렬이 진행되기 때문에 특정 문자열 바로 뒷 문자와 접두어 관계일 것이다.

  • 따라서 바로 뒷 문자의 앞부분이 같은 지 확인을 해서 같으면 접두어를 포함하는 것.

• 정렬을 할때 사전순으로 정렬이 된다는 거를 까먹지 말자.

알고리즘

• Sort

CODE

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

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());
        StringBuilder sb = new StringBuilder();

        String[] phone;
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            phone = new String[N];
            for (int idx = 0; idx < N; idx++) {
                phone[idx] = br.readLine();
            }
            Arrays.sort(phone);

            if (isContains(N, phone)) {
                sb.append("YES\n");
            } else {
                sb.append("NO\n");
            }
        }
        System.out.println(sb);

    }

    //포함여부 확인
    //포함이 되어있다면 일관성이 없으므로 false
    //포함이 되어있지 않다면 일관성이 있으므로 true
    private static boolean isContains(int n, String[] phone) {

        for(int idx = 0; idx <n-1;idx++){
            if(phone[idx+1].startsWith(phone[idx])){
                return false;
            }

        }

        return true;
    }
}