๊ธฐ๋ก๋ฐฉ

BOJ_5052 : ์ „ํ™”๋ฒˆํ˜ธ ๋ชฉ๋ก ๋ณธ๋ฌธ

CodingTest/Java

BOJ_5052 : ์ „ํ™”๋ฒˆํ˜ธ ๋ชฉ๋ก

Soom_1n 2024. 5. 19. 00:55

๐Ÿ‘‰ ๋ฌธ์ œ๋งํฌ



๐Ÿ”ธ ๋ฌธ์ œ ๋ถ„์„ ๐Ÿ”ธ

  • t ๋ฒˆ์˜ ํ…Œ์ŠคํŠธ ๋™์•ˆ n ๊ฐœ์˜ ์ „ํ™”๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ์ „ํ™”๋ฒˆํ˜ธ๊ฐ€ ์„œ๋กœ ์ ‘๋‘์–ด๊ฐ€ ๋˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ์—†๋Š”์ง€ ํŒ๋‹จํ•œ๋‹ค.
  • ์ ‘๋‘์–ด ๊ด€๊ณ„๊ฐ€ ์žˆ์œผ๋ฉด NO, ์—†์œผ๋ฉด YES๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ”ธ ๋ฌธ์ œ ํ’€์ด ๐Ÿ”ธ

  • n๊ฐœ์˜ ๋ฌธ์ž์—ด๋“ค์„ ์„œ๋กœ ๋น„๊ตํ•ด์•ผํ•˜๋Š”๋ฐ, n์ด 1๋งŒ์ด๋ฏ€๋กœ O(n^2)์œผ๋กœ ๋น„๊ตํ•˜๋ฉด ํ…Œ์ŠคํŠธ์ผ€์ด์Šค๊นŒ์ง€ ํ•ฉ์ณ์„œ 1์ดˆ๋ฅผ ์ดˆ๊ณผํ•˜๊ฒŒ ๋œ๋‹ค.
  • ๋ฐฉ๋ฒ•์€ 2๊ฐ€์ง€๊ฐ€ ์žˆ๋Š”๋ฐ ์ •๋ ฌ ํ˜น์€ ํŠธ๋ผ์ด ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ด์šฉํ•˜๋Š” ๊ฒƒ์ด๋‹ค.
    • ์ •๋ ฌ : ํ˜„์žฌ ๋ฌธ์ž์—ด๋ณด๋‹ค ๊ธด ๋ฌธ์ž์—ด ํ•˜๊ณ ๋งŒ ๋น„๊ตํ•ด์„œ ์ ‘๋‘์–ด์ธ ๊ฒฝ์šฐ๊ฐ€ ์žˆ๋Š”์ง€ ํŒŒ์•…ํ•œ๋‹ค.
    • ํŠธ๋ผ์ด : ํ˜„์žฌ ๋ฌธ์ž์—ด์„ ์ ‘๋‘์–ด๋กœ ํ•˜๊ฑฐ๋‚˜, ๋‹ค๋ฅธ ๋ฌธ์ž์—ด์ด ํ˜„์žฌ ๋ฌธ์ž์—ด์—๊ฒŒ ์ ‘๋‘์–ด์ธ์ง€ ํ™•์ธํ•œ๋‹ค.

๐Ÿ”ธ ์ •๋ ฌ ํ’€์ด ์ฝ”๋“œ ๐Ÿ”ธ

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;

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

        int T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {

            int n = Integer.parseInt(br.readLine());
            char[][] chars = new char[n][];

            for (int i = 0; i < n; i++) {
                chars[i] = br.readLine().toCharArray();
            }

            Arrays.sort(chars, Comparator.comparingInt(o -> o.length));

            if ((checkStrs(chars)))
                sb.append("YES\n");
            else
                sb.append("NO\n");
        }
        bw.write(sb.toString());
        bw.flush();
    }

    private static boolean checkStrs(char[][] chars) {
        for (int i = 0; i < chars.length; i++) {
            for (int j = i + 1; j < chars.length; j++) {
                if (isPrefix(chars[i], chars[j]))
                    return false;
            }
        }
        return true;
    }

    private static boolean isPrefix(char[] cs1, char[] cs2) {
        for (int i = 0; i < cs1.length; i++) {
            if (cs1[i] != cs2[i])
                return false;
        }
        return true;
    }
}

๐Ÿ”ธ ์ฝ”๋“œ ํ•ด์„ ๐Ÿ”ธ

  • n๊ฐœ์˜ ๋ฌธ์ž์—ด์„ ๋ชจ๋‘ ์ž…๋ ฅ๋ฐ›๊ณ , ๊ธธ์ด๋กœ ์ •๋ ฌ ํ›„์— ์ ‘๋‘์–ด ๊ด€๊ณ„๊ฐ€ ์žˆ๋Š”์ง€ ํŒŒ์•…ํ•œ๋‹ค.
  • checkStrs() ๋ฉ”์„œ๋“œ์—์„œ ํ˜„์žฌ ๋ฌธ์ž์—ด๋ณด๋‹ค ๋’ท ์ธ๋ฑ์Šค์˜ ๋ฌธ์ž์—ด์„ ๋น„๊ตํ•œ๋‹ค. ๊ธธ์ด๊ฐ€ ๋” ๊ธธ๊ฑฐ๋‚˜ ๊ฐ™์€ ๋ฌธ์ž์—ด๋งŒ ๋น„๊ตํ•  ์ˆ˜ ์žˆ๊ฒŒ ๋œ๋‹ค.
  • isPrefix() ๋ฉ”์„œ๋“œ์—์„œ ๋ฌธ์ž๋ฅผ ํ•˜๋‚˜์”ฉ ๋น„๊ตํ•˜๋Š”๋ฐ, String.charAt()์€ ํšจ์œจ์ด ๋‚˜์˜๋ฏ€๋กœ char[] ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ–ˆ๋‹ค.

 

๐Ÿ”ธ ํŠธ๋ผ์ด ํ’€์ด ์ฝ”๋“œ ๐Ÿ”ธ

import java.io.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {

            int n = Integer.parseInt(br.readLine());
            Trie trie = new Trie();
            boolean isConsistent = true;

            for (int i = 0; i < n; i++) {
                if (!trie.insert(br.readLine().toCharArray()))
                    isConsistent = false;
            }
            if (isConsistent)
                sb.append("YES\n");
            else
                sb.append("NO\n");
        }
        bw.write(sb.toString());
        bw.flush();
    }

    private static class Trie { // ํŠธ๋ผ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜

        private final Node rootNode = new Node(); // ๋ฃจํŠธ ๋…ธ๋“œ ์‹ฑ๊ธ€ํ†ค ์ƒ์„ฑ

        public boolean insert(char[] chars) {
            Node node = rootNode; // ๋ฃจํŠธ ๋…ธ๋“œ๋ถ€ํ„ฐ ์‹œ์ž‘
            boolean isNewNodeCreated = false;

            for (char c : chars) { // ํ•ด๋‹น key๊ฐ€ ์—†์œผ๋ฉด ๋งŒ๋“ค์–ด ๋ฐ˜ํ™˜, ์žˆ์œผ๋ฉด ๊ทธ value๋ฅผ ๋ฐ˜ํ™˜
                if (!node.chiledNode.containsKey(c)) {
                    node.chiledNode.put(c, new Node());
                    isNewNodeCreated = true;
                }
                node = node.chiledNode.get(c);
                if (node.isEnd) { // ๋‹ค๋ฅธ ๋ฒˆํ˜ธ๊ฐ€ ์ด ๋ฒˆํ˜ธ์˜ ์ ‘๋‘์–ด์ž„
                    return false;
                }
            }

            if (!isNewNodeCreated) {
                return false; // ์ด ๋ฒˆํ˜ธ๊ฐ€ ๋‹ค๋ฅธ ๋ฒˆํ˜ธ์˜ ์ ‘๋‘์–ด์ž„
            }

            node.isEnd = true; // ๋ฌธ์ž์—ด์˜ ๋งˆ์ง€๋ง‰์ด ๋˜๋Š” ๋…ธ๋“œ์ž„
            return true;
        }
    }

    private static class Node {
        final Map<Character, Node> chiledNode;
        boolean isEnd;

        public Node() {
            this.chiledNode = new HashMap<>();
            this.isEnd = false;
        }
    }
}

๐Ÿ”ธ ์ฝ”๋“œ ํ•ด์„ ๐Ÿ”ธ

  • ํŠธ๋ผ์ด ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์‘์šฉํ•ด์„œ ํŠธ๋ฆฌ์— ๋ฌธ์ž์—ด์„ ์ €์žฅํ•จ๊ณผ ๋™์‹œ์— ์ ‘๋‘์–ด ๊ด€๊ณ„์ธ์ง€ ํŒŒ์•…ํ•œ๋‹ค.
  • ํŠธ๋ผ์ด ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ๋ฌธ์ž์—ด์„ ํŠธ๋ฆฌ ๊ตฌ์กฐ๋กœ ์ €์žฅํ•ด์„œ ๊ฒ€์ƒ‰์„ ํšจ์œจ์ ์œผ๋กœ ํ•  ์ˆ˜ ์žˆ๊ฒŒํ•œ๋‹ค.
    • ๋ฌธ์ž ํ•˜๋‚˜์”ฉ map์˜ key๋กœ ๋งตํ•‘ํ•˜๊ณ  value๋Š” ์ž์‹ ๋…ธ๋“œ์ด๋‹ค.
    • ํ˜„์žฌ ๋…ธ๋“œ๊ฐ€ ๋ฌธ์ž์—ด์˜ ๋งˆ์ง€๋ง‰์ด ๋˜๋Š” ๋…ธ๋“œ์ด๋ฉด boolean ๋ณ€์ˆ˜ isEnd๋ฅผ true๋กœ ์ €์žฅํ•œ๋‹ค.
  • ๋ฌธ์ž์—ด์„ ํŠธ๋ผ์ด์— ์ €์žฅํ•  ๋•Œ isEnd๊ฐ€ true์ธ ๊ฒฝ์šฐ๋ฅผ ๋ฐœ๊ฒฌํ•˜๋ฉด, ๋‹ค๋ฅธ ๋ฌธ์ž์—ด์ด ํ˜„์žฌ ๋ฌธ์ž์—ด์˜ ์ ‘๋‘์–ด๊ฐ€ ๋˜๋Š” ๊ฒฝ์šฐ์ด๋‹ค.
  • ๋ฌธ์ž์—ด ์ €์žฅ์„ ๋งˆ์ณค๋Š”๋ฐ, ์ƒˆ๋กœ ์ƒ์„ฑ๋œ ๋…ธ๋“œ๊ฐ€ ์—†์œผ๋ฉด, ํ˜„์žฌ ๋ฌธ์ž์—ด์ด ๋‹ค๋ฅธ ๋ฌธ์ž์—ด์˜ ์ ‘๋‘์–ด๊ฐ€ ๋œ ๊ฒฝ์šฐ์ด๋‹ค.

๐Ÿ”ธ end ๐Ÿ”ธ

  • ์ฒ˜์Œ์—” Bruete Force๋กœ ๋ชจ๋“  ๋ฌธ์ž์—ด์„ contains๋กœ ๋น„๊ตํ–ˆ๋Š”๋ฐ ๋ฉ”๋ชจ๋ฆฌ ์ดˆ๊ณผ๊ฐ€ ๋‚ฌ๋‹ค.
  • ํƒœ๊ทธ๋ฅผ ์‚ดํŽด๋ณด๋‹ˆ ์ •๋ ฌ์ด ์žˆ์–ด์„œ ์กฐ๊ธˆ ๊ณ ๋ฏผ ํ›„, ๊ธธ์ด ์ •๋ ฌ๋กœ ๊ฐ„๋‹จํžˆ ํ’€์ดํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค.
    • ์ •๋ ฌ ์ •๋„์˜ ํ’€์ด๋Š” ๊ผญ ์ฒ˜์Œ๋ถ€ํ„ฐ ๊ณ ๋ คํ•ด ๋ณด๋„๋ก ํ•˜์ž.
  • ํƒœ๊ทธ์— ํŠธ๋ผ์ด๋ผ๋Š” ๊ฒƒ๋„ ์žˆ๊ธธ๋ž˜ ์ž๋ฃŒ๊ตฌ์กฐ ์ด๋ก ์„ ์‚ดํŽด๋ณธ ๋’ค ์ƒˆ๋กญ๊ฒŒ ํฌ์ŠคํŒ… ์ •๋ฆฌ ํ›„ ํ’€์ด์—๋„ ์ ์šฉํ•ด ๋ณด์•˜๋‹ค.
    • ์ƒˆ๋กญ๊ฒŒ ๋ฌธ์ž์—ด ์ฒ˜๋ฆฌ ๋ฐฉ๋ฒ•์„ ์•Œ๊ฒŒ ๋˜์–ด์„œ ์ข‹์€ ๊ณต๋ถ€๊ฐ€ ๋œ ๊ฒƒ ๊ฐ™๋‹ค.

728x90