[Gold IV] 전화번호 목록 - 5052 (JAVA)

문제 요약

 

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

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

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

---

문제 분석

전체 전화번호를 사전순으로 정렬한 후, i번째가 i+1번째의 앞에 포함되는지 반복문을 통해 확인한다.

---

코드

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());
        // 테스트케이스 개수만큼 반복
        for(int t = 0; t < T; t++){
            int N = Integer.parseInt(br.readLine());
            String[] arr = new String[N];
            for(int n = 0; n < N; n++){
                arr[n] = br.readLine();
            }
            // 들어가 있는 단어들을 사전순으로 정렬
            Arrays.sort(arr);
            boolean result = true;
            // 처음부터 끝까지 모든 번호들을 탐색
            // 순서대로 2개씩 확인할것이기때문에 list.size-1로 지정
            /*
                배열 안에 11, 1231, 11312, 1345, 1111 이런 5개의 문자열이 있다고 해보자.
                이를 사전순으로 정렬하면 다음과 같이 나온다.
                [11, 1111, 11312, 1231, 1345]
                이렇게 사전순으로 정렬을 하게되면, 접두어를 기준으로 탐색하기 수월하게 나온다.
                위 예시에서 11이 들어가있는 친구는 1111, 11312 이렇게 두개이지만
                문제 조건에 따라 한개라도 불만족하면 false이기 때문에 바로 break때려준다.
             */
//            System.out.println(Arrays.toString(arr));
            for(int i = 0; i < arr.length-1; i++){
                // 현재 번호가 다음 번호의 접두어인지 확인해야하기 때문에
                // startWith를 사용하여 확인한다.
                if(arr[i+1].startsWith(arr[i])){
                    result = false;
                    break;
                }
            }
            System.out.println(result ? "YES" : "NO");
        }
    }
}

---

정리

새로 배운 내용

없음

개선할 점

문제를 제대로 안 읽어서 포함 여부를 확인하는데 contains를 쓰다가 틀렸다.

더 찾아볼만한 사항

Trie라는 자료구조가 태그로 달려있던데 이게 뭔지 모르겠다.

---