[BOJ/백준][JAVA] 5052 - 전화번호 목록

문제

5052번: 전화번호 목록

📒 문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 

📒 해결 방법

이 문제는 사실 Trie로 푸는 방법이 대체적이라고 한다. 하지만 아직 나는 트라이가 익숙하지 않기에 StartsWith를 사용해서 앞에서부터 문자를 확인하고 온전히 겹치는 것을 확인해 boolean값을 체크하는 형식으로 해결했다!

💡 StartsWith : 비교대상 문자열. startsWith("체크할 문자열")
즉, 비교할 문자열이 체크할 문자열의 값으로 시작되는 확인

📒 소스 코드

package BOJ.Sort;

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

public class boj5052_전화번호목록 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            int size = Integer.parseInt(br.readLine());

            int min_size = Integer.MAX_VALUE;
            String[] input = new String[size];
            for (int i = 0; i < size; i++) {
                input[i] = br.readLine();
            }
            Arrays.sort(input);

            boolean flag = false;
            for (int i = 0; i < size - 1; i++) {
                if (input[i + 1].startsWith(input[i])) {
                    flag = true;
                }
            }

            if (flag) {
                System.out.println("NO");
            } else {
                System.out.println("YES");
            }
        }
    }
}

 

📒 리뷰

내 제출

 

---

처음엔 Contains를 사용해서 문제를 해결하니까 바로 틀렸습니다가 떴다.
비교 형식으로 Contains를 사용하게 되면 겹치는 문자열이 중간에 들어가 있기만 해도 제대로 된 일관성 boolean이 확인되지 않기 때문이다
다음엔 Trie로 풀어봐야징..🐯🐯