[BOJ-5052][Trie] 전화번호 목록 - Java

문제 바로가기

5052번: 전화번호 목록

 

트라이를 활용하는 가장 기본적인 문제인가봅니다. 백준 트라이 태그에 젤 위에 있는 문젭니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; i++) {
            Trie trie = new Trie();
            boolean flag = true;

            int n = Integer.parseInt(br.readLine());
            for(int j = 0; j < n; j++) {
                if(!trie.insert(br.readLine())) {
                    flag = false; continue;
                }
            }
            sb.append(flag == true ? "YES\n" : "NO\n");
        }
        System.out.println(sb.toString());
    }

    static class TrieNode {
        Map<Character, TrieNode> childNodes = new HashMap<>();
        boolean isLast;
    }

    static class Trie {
        TrieNode root = new TrieNode();

        boolean insert(String word) {
            TrieNode thisNode = root;
            for(int i = 0; i < word.length(); i++) {
                char n = word.charAt(i);
                if(thisNode.childNodes.get(n) == null) {
                    thisNode.childNodes.put(n, new TrieNode());
                }
                thisNode = thisNode.childNodes.get(n);
                if(thisNode.isLast == true) return false;
            }
            if(thisNode.childNodes.size() != 0) return false;
            thisNode.isLast = true;
            return true;
        }
    }
}

이전에 풀었던 문제들과 궤를 같이 합니다.

기본적으로 HashMap을 활용해서 트라이를 만들어줍니다.

 

그리고 전화번호를 받을 때 바로 가능한지 체크해주기 위해 insert() 메소드에 그 부분을 추가했습니다.

예를 들어 123이 먼저 들어왔고, 12345가 그 뒤에 들어오면 3을 찾았을 때 3 노드의 isLast 값이 true 이기 때문에 바아로 false 를 리턴해주면 됩니다.

 

반대 경우에는 for문을 다 돌고나서 체크해줍니다. 123 다 찾고나서 그 밑에 다른 친구가 더 있으면 마찬가지로 false를 리턴해줍니다.

 

 

트라이 좋다! 감사합니다!!