[백준] 5052번 - 전화번호 목록 JAVA 풀이

문제

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

5052번: 전화번호 목록

 

문제 요약

전화번호 목록이 주어졌을 때 911, 91 12 54 26 처럼 접두사가 같은 번호는 일관성이 없는 목록으로, 이런 경우 출력을 NO 로, 나머지 경우는 YES를 출력한다.

즉, 예제의 경우에서는 "911"과 일치하는 문자열이 있으면 안된다는 뜻이다.

 

입력 및 출력

 

문제 접근

테스트케이스 개수, 테스트케이스 당 전화번호 수, 전화번호 길이를 종합해 보았을 때, 완전탐색으로는 시간 제한을 지킬 수 없을 것 같았다.  완전탐색을 할 시에는 아래 그림과 같이 하나의 전화번호를 선정하고, 나머지 전화번호와 비교하는 수행을 반복해야 한다.

그렇다면 수행하는데 필요한 평균적인 연산 횟수는 대략 N-1(N-2) 일 것이다. 최대로 들어올 수 있는 전화번호 개수가 10000개, 9999*9998 = 99,970,002 이고, 테스트케이스가 최대 50개이니, 99,970,002 * 50  = 4,998,500,100 이다.

자바는 평균적으로 1초에 1억번 연산을 할 수 있기 때문에 완전탐색으로는 해당 문제의 조건을 맞출 수 없다. 

 

그렇기 때문에 해당 문제에서는 저장, 탐색 효율이 높은 트리를 사용해야 한다.

트리 중에서도 문자열을 저장할 때 효율적으로 사용할 수 있는 Trie(트라이) 자료구조가 있다.  

검색할 때 자동완성 기능이나, 사전 검색 등에서 사용되는 자료구조로 문자열을 검색하는데 특화되어있다.

해당 문제에 Trie 자료구조를 적용해보자면 아래 그림과 같다. 

9112 , 91125, 911254, 9112542, 91125426 까지 노드가 생길 것이고, 오른쪽 서브트리인 9762 ... 도 가지가 쭉 뻗어나가서마지막 리프노드는 97625999가 될 것이다. 

이렇게 Trie가 만들어졌을 때, 하나의 서브트리에서 리프노드 또는, 리프노드 "였던" 노드가 2개 이상이라면 일관성을 지키지 못한 경우가 된다. 

위의 예제에서도 911254가 입력으로 들어오기 전 까지는 "911"이 리프노드 였을 것이다. 

 

그렇기 때문에, 하나의 노드는 자기 자신의 값과, 그 다음 노드, 리프노드 판단 여부 변수 를 가지고 있어야 한다.

class TrieNode{
	String value;
    int endNode;
    private Map<String,TrieNode> childNode = new HashMap<>();
    }

맨 상위 root 노드인 TrieNode 객체는 value 를 -1로 가지도록 한다. 

"911" 입력을 예시로 들어 설명해보겠다. 

이 value가 -1인 TrieNode의 childNode에 문자열을 하나 넣는 것을 시도한다. 해당 예제에서는 key가 9이고, value가 TrieNode 객체인 HashMap이 들어가게 될 것이다.   

입력 "9"에 대한 처리가 끝났다. 이제 다음에 처리할 노드는 root node에 붙은 key값이 9인 노드, 즉 1번 노드의 child가 될 것이다.

이제 "1"을 처리한다. 이전 키 값이 9 였으니, 여기에 지금의 입력을 문자열 덧셈하여 "91"로 만든다. 이것을 key로 사용할 것이다.  1번 노드의 childeNode는 key가 91인 HashMap이 된다. 

마지막 입력인 "1" 도 위의 처리와 똑같다. 앞에서의 key 값이 "91" 이었으니, 이번 입력에서는 key가 "911" 이고, 2번 노드의 childNode로 붙게 된다. 이번 입력이 "911" 의 마지막 문자열이기 때문에, 리프노드임을 알리기 위해 endNode 값을 -1로 설정한다.

 

이번엔 "91125426" 이라는 입력이 들어왔을 때를 생각해보자.

이미 Trie는 위처럼 구성되어있기 때문에 9, 91, 911 이라는 key 값은 존재한다. 그렇기 때문에 911까지는 그저 자식 노드를 타고 들어오기만 한다. 

자식 노드를 타고 들어온다는 뜻은,

  trieNode = trieNode.getChild().get(key);

처럼, trieNode가 부모 노드일 때 자식 노드에 대한 처리를 끝마치고 이 자식 노드를 부모 노드로 치환해주는 것이다.

그렇다면 1번 노드가 부모일 때 2번 노드가 자식으로 붙고, 다시 2번 노드가 부모가 되어 3번 노드를 자식으로 가지는 구조가 된다. (그림처럼) 

3번 노드에 도달했을 때, "2" 라는 입력을 childNode에 key는 9112, value는 new ChildNode 로 붙이게 된다.

이렇게 쭉 등록 작업을 하게될 것이다. 

그렇다면 입력받은 전화번호의 일관성 여부는 어떻게 판단할 것인가?

등록을 할 때 endNode 값이 -1인 것을 카운트 해 줄 것이다.

특정 전화번호 등록이 끝났을 때 해당 전화번호(ex: 91125426) 노드는 무조건 endNode이기 때문에 일관성이 있는 경우라면 endNode의 개수가 1개, 그렇지 않다면 endNode의 개수가 2개 이상일 것이다. 

 

위의 예제에서도 91125426을 등록하는 중에 3번 노드, 그리고 표현하지는 않았지만 key값이 91125426인 노드, 총 2개의 endNode를 발견할 수 있다.

 

이때 주의해야 할 점은 무조건 길이가 짧은 입력부터 처리해야 한다는 것이다. 

91125426, 911 순으로 들어오는 경우에는 91125426 등록할 때 end node 하나 발견, 911 들어올 때 end node 하나 발견 으로 일관성 여부를 판단할 수 없게 된다.

911, 91125426 순으로 들어와야 91125426을 등록할 때 이미 처리된 911의 end node를 발견할 수 있다. 

 

전체 코드

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

class TrieNode { //Trie 클래스
    String value;
    int endNode; //리프 노드인 경우 -1의 값을 가짐

    private Map<String, TrieNode> childNode = new HashMap<>(); //자식 노드를 저장함

    public Map<String, TrieNode> getChild() {
        return childNode;
    }

    public void setEndNode(int endNode) {
        this.endNode = endNode;
    }

    public TrieNode(String value) {
        this.value = value;
    }

    public TrieNode() {
    }
}

class Trie {
    private final TrieNode root;

    public Trie() {
        this.root = new TrieNode("-1"); // root 노드
    }

    public boolean isConsistent(String[] inputStrings) {
        //문자열 길이가 짧은 순서대로 sort
        Arrays.sort(inputStrings, Comparator.comparingInt(String::length));

        for (String input : inputStrings) {
            if (!insert(input)) {
                return false;
            }
        }
        return true;
    }

    private boolean insert(String word) {
        //문자열을 하나하나 떼서 String 배열로 만듦.
        String[] input = word.split("");
        TrieNode trieNode = root; //trieNode는 데이터가 계속 덧씌워질 객체이다.
        StringBuilder addString = new StringBuilder(); //key 를 생성하기 위한 변수이다.

        for (int l = 0; l < input.length; l++) {
            //이전 key를 이번 입력 문자와 합쳐서 key 생성
            addString.append(input[l]);
            String key = addString.toString();

            if (!trieNode.getChild().containsKey(key)) { //만약 child에 해당 key가 존재하지 않는다면
                trieNode.getChild().put(key, new TrieNode(key)); //등록해준다.
            }

            if (trieNode.endNode == -1) { //해당 노드가 endNode, 즉 리프노드인지 확인한다.
                return false;
            }

            if (l == input.length - 1) { //이번 입력의 끝에 도달하면 해당 노드가 리프 노드임을 기록한다.
                trieNode.getChild().get(key).endNode = -1;
            }

            trieNode = trieNode.getChild().get(key); //child를 부모로 설정하여 다음 child를 붙일 수 있도록 한다.
        }

        return true;
    }
}

public class Main {
    static int T;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());

        //테스트케이스 개수만큼 수행
        for (int i = 0; i < T; i++) {
            processTestCase(br);
        }
    }

    private static void processTestCase(BufferedReader br) throws IOException {
        N = Integer.parseInt(br.readLine());
        String[] input_s = new String[N]; //문자열 길이가 짧은 순서대로 정렬하기 위한 변수

        for (int j = 0; j < N; j++) { //N번째 입력 처리
            input_s[j] = br.readLine();
        }

        Trie trie = new Trie();
        boolean consistency = trie.isConsistent(input_s); // 일관성 여부 확인

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