๐Ÿ“– [๋ฐฑ์ค€์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ’€์ด] Q.5052 ์ „ํ™”๋ฒˆํ˜ธ ๋ชฉ๋ก ๋ฌธ์ œ ํ’€์ด - java

๐Ÿ“– ๋ฌธ์ œ

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

์ „ํ™”๋ฒˆํ˜ธ ๋ชฉ๋ก์ด ์ฃผ์–ด์ง„๋‹ค. ์ด๋•Œ, ์ด ๋ชฉ๋ก์ด ์ผ๊ด€์„ฑ์ด ์žˆ๋Š”์ง€ ์—†๋Š”์ง€๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ „ํ™”๋ฒˆํ˜ธ ๋ชฉ๋ก์ด ์ผ๊ด€์„ฑ์„ ์œ ์ง€ํ•˜๋ ค๋ฉด, ํ•œ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ค๋ฅธ ๋ฒˆํ˜ธ์˜ ์ ‘๋‘์–ด์ธ ๊ฒฝ์šฐ๊ฐ€ ์—†์–ด์•ผ ํ•œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ์ „ํ™”๋ฒˆํ˜ธ ๋ชฉ๋ก์ด ์•„๋ž˜์™€ ๊ฐ™์€ ๊ฒฝ์šฐ๋ฅผ ์ƒ๊ฐํ•ด๋ณด์ž

  • ๊ธด๊ธ‰์ „ํ™”: 911
  • ์ƒ๊ทผ: 97 625 999
  • ์„ ์˜: 91 12 54 26

์ด ๊ฒฝ์šฐ์— ์„ ์˜์ด์—๊ฒŒ ์ „ํ™”๋ฅผ ๊ฑธ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์ด ์—†๋‹ค. ์ „ํ™”๊ธฐ๋ฅผ ๋“ค๊ณ  ์„ ์˜์ด ๋ฒˆํ˜ธ์˜ ์ฒ˜์Œ ์„ธ ์ž๋ฆฌ๋ฅผ ๋ˆ„๋ฅด๋Š” ์ˆœ๊ฐ„ ๋ฐ”๋กœ ๊ธด๊ธ‰์ „ํ™”๊ฐ€ ๊ฑธ๋ฆฌ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

๋”ฐ๋ผ์„œ, ์ด ๋ชฉ๋ก์€ ์ผ๊ด€์„ฑ์ด ์—†๋Š” ๋ชฉ๋ก์ด๋‹ค.

๐Ÿ” ์ ‘๊ทผ๋ฒ•

Q.5052 ์ „ํ™”๋ฒˆํ˜ธ ๋ชฉ๋ก ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

์ฃผ์–ด์ง„ ๋ฌธ์ œ์˜ ์˜ˆ์‹œ๋ฅผ ๋ณด๋ฉด ํ•œ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ค๋ฅธ ๋ฒˆํ˜ธ์˜ ์ ‘๋‘์–ด์ธ ๊ฒฝ์šฐ๊ฐ€ ์—†์–ด์•ผํ•ฉ๋‹ˆ๋‹ค.

Trie๋ฅผ ์ด์šฉํ•˜์—ฌ ํ’€์ด๊ฐ€ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

Trie๋ฅผ ์ด์šฉํ•˜์—ฌ ์ „ํ™”๋ฒˆํ˜ธ ๋ชฉ๋ก๋“ค์„ ์ž…๋ ฅํ•˜๋Š”๋ฐ

์ „ํ™”๋ฒˆํ˜ธ ์ž…๋ ฅ ๋ฐ›๋Š” ๋„์ค‘์— ์ด๋ฏธ ์™„์„ฑ ๋œ ์ „ํ™”๋ฒˆํ˜ธ๊ฐ€ ์žˆ๋‹ค๋ฉด

ex) 911 ์ด ์ด๋ฏธ ์ž…๋ ฅ ๋˜์–ด์žˆ๊ณ 
์„ ์˜์ด์˜ ์ „ํ™”๋ฒˆํ˜ธ๊ฐ€ ์ž…๋ ฅ์ด ๋  ๋•Œ
911 -25426 ์ด๋ฏธ 911์—์„œ ๊ธด๊ธ‰์ „ํ™” 911์˜ ๋ฒˆํ˜ธ๊ฐ€ ์™„์„ฑ๋˜๋ฒ„๋ฆผ  

ํ•œ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ค๋ฅธ ๋ฒˆํ˜ธ์˜ ์ ‘๋‘์–ด์ธ ๊ฒฝ์šฐ์ด๋ฏ€๋กœ ์ผ๊ด€์„ฑ์ด ์—†๋Š” ๋ชฉ๋ก์ž„์„ ์•Œ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ด๋ฅผ ์ด์šฉํ•ด ๋ฌธ์ œ ํ’€์ด๊ฐ€ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

๐Ÿ’ป ์ฝ”๋“œ


package problem.string.trie;

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

public class Main_5052 {

    static int t,n;
    static Trie trie;
    static StringBuilder sb = new StringBuilder();
    static String[] phoneNumbers;

    public static void main(String[] args) throws IOException {
        input();
        System.out.println(sb.toString());
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        for(int i=0; i<t; i++) {
            trie = new Trie();
            n = Integer.parseInt(br.readLine());
            phoneNumbers = new String[n];
            for(int j=0; j<n; j++){
                phoneNumbers[j] = br.readLine();
            }
            solve();
        }
        br.close();
    }

    public static void solve() {
        Arrays.sort(phoneNumbers);
        for(int i=0; i<n; i++){
            if (trie.insert(phoneNumbers[i]) == false) {
                sb.append("NO\n");
                return;
            }
        }
        sb.append("YES\n");
    }

    static class TrieNode {

        public Map<Character, TrieNode> childNodes = new HashMap<>();
        private boolean isLastChar;

        public Map<Character, TrieNode> getChildNodes() {
            return this.childNodes;
        }

        public boolean isLastChar() {
            return this.isLastChar;
        }

        public void setLastChar(boolean lastChar) {
            this.isLastChar = lastChar;
        }
    }

    static class Trie {
        private TrieNode rootNode;

        public Trie() {
            rootNode = new TrieNode();
        }

        // ์ž์‹ ๋…ธ๋“œ ์ถ”๊ฐ€
        boolean insert(String word) {
            TrieNode thisNode = this.rootNode;

            for (int i = 0; i < word.length(); i++) {
                char currentChar = word.charAt(i);
                if(thisNode.childNodes.get(currentChar) == null){
                    thisNode.childNodes.put(currentChar,new TrieNode());
                }
                thisNode = thisNode.childNodes.get(currentChar);
                if(thisNode.isLastChar == true)
                    return false;
            }
            thisNode.setLastChar(true);
            return true;
        }
    }
}

Written on April 5, 2021