94. 전화번호 목록 (백준 5052) [JAVA]

 

 

1. 문제

문제 링크 : https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	256MB	23770	7378	4280	29.501%

문제

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

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

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

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

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

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

2. 풀이

일일히 번호들을 직접 비교하려하면 $O(N^{10})$으로 시간이 너무 오래걸린다.

번호를 비교하는 방법을 생각해보다가, 각각의 번호를 징검다리의 좌표로 생각하고, 한글자씩 이동한다고 생각해보았다.

이런식으로 결국 트리 모양의 징검다리가 만들어지는데 하나하나 연결리스트로 경로를 만들고 마지막에 갈 수 있는 징검다리가 있으면 나를 포함하는 번호가 있는 것이므로 일관성이 없는 것이다.

만약 한 숫자라도 기존에 있는 숫자가 아니면, 새 징검다리 경로를 만들 것이므로 일관성이 있을 것이다.

징검다리는 숫자가 긴 번호순으로 만드는게 구현에 편해서, 우선순위 큐에 역순을 적용해서 번호를 입력받았다.

각각의 징검다리는 Node로 구현해서 각각의 자식들을 가질 수 있게 했고, 재귀를 사용해서 트리를 구현하였다.

 

3. 코드

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

public class Main {

    //짧은 애가 포함이 되면 안됨. 

    static int t;
    static int n;
    static PriorityQueue<String> numbers;
    static boolean answer;
    static ArrayList<String> answerList = new ArrayList<String>();

    public static void main(String[] args) throws IOException{
        BufferedReader br = new java.io.BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

            t = Integer.parseInt(br.readLine());

            for(int i=0; i<t; i++) {
                n = Integer.parseInt(br.readLine());

                numbers = new PriorityQueue<>(Collections.reverseOrder());
                for(int j=0; j<n; j++) {
                    numbers.add(br.readLine());
                }
                makeTree();

                if(answer) {
                    answerList.add("YES");
                }else {
                    answerList.add("NO");
                }
            }

            //정답 출력
            for(String s : answerList) {
                System.out.println(s);
            }
        }

    public static void makeTree() {
        ArrayList<Node> tree = new ArrayList<Node>();
        answer = true;

        while(!numbers.isEmpty()) {
            String num = numbers.poll();
            makeTree(num, tree);
        }
    }

    public static int findChild(ArrayList<Node> childs, int cur) {
        for(int i = 0; i<childs.size(); i++) {
            if(childs.get(i).current == cur) {
                return i;
            }
        }
        return -1;
    }

    public static void makeTree(String number, ArrayList<Node> tree) {    

        int cur = number.charAt(0)-'0';
        number = number.substring(1);
        int next = findChild(tree,cur);

        //1개 남았을 때 -> 다음 녀석이 자식이 있으면 (계속되면) 일관성 x
        if(number.length() == 0) {
            if(next != -1) {
                answer = false;
            }
            return;
        }


        if(next != -1) {
            makeTree(number, tree.get(next).childs);
        }

        else {
            Node child = new Node(cur);
            tree.add(child);
            makeTree(number, child.childs);
        }
    }
}

class Node{
    int current;
    ArrayList<Node> childs;

    public Node(int cur) {
        this.current = cur;
        childs = new ArrayList<Node>();
    }
}

 

4. 결과

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!