[BOJ]5052번 : 전화번호 목록

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

5052번: 전화번호 목록

 

분류 : 해싱 , 트라이, 정렬

 

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

public class Main {
    static Myscanner sc = new Myscanner();
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static void main(String[] args) throws IOException {

        int TC = sc.nextInt();
        while (TC-- > 0) {
            int PhN = sc.nextInt();
            String[] str = new String[PhN];
            for (int i = 0; i < PhN; i++) {
                str[i] = sc.next();
            }
            Arrays.sort(str);
            String ans = "YES";
            for (int i = 1; i < PhN; i++) {
                if (str[i].length() >= str[i - 1].length()
                        && str[i - 1].equals(str[i].substring(0, str[i - 1].length()))) {
                    ans = "NO";
                    break;
                }
            }
            out.println(ans);
        }
        out.flush();
    }
}

class Myscanner {
    BufferedReader br;
    StringTokenizer st;

    Myscanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str += br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

 

String을 사전 순으로 정렬한 후에 이전 단어와 현재 단어의 길이 비교 , 이전 단어가 현재 단어와 일치하는지 판단하는 방식으로 접근했다.

테스트 케이스가 약한 것인지 시간 초과를 걱정했지만 우려와는 다르게 통과하였고,

 

분류에 있는 "트라이"를 이용해서 추후에 다시 풀어 볼 예정

 

추가적으로, Java는 다른 방법으로 밑의 방법처럼 startsWith 메서드를 이용하여 풀 수도 있다.