BOJ_5052 : 전화번호 목록

👉 문제링크

---

---

🔸 문제 분석 🔸

• 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로 비교했는데 메모리 초과가 났다.
• 태그를 살펴보니 정렬이 있어서 조금 고민 후, 길이 정렬로 간단히 풀이할 수 있었다.
  • 정렬 정도의 풀이는 꼭 처음부터 고려해 보도록 하자.
• 태그에 트라이라는 것도 있길래 자료구조 이론을 살펴본 뒤 새롭게 포스팅 정리 후 풀이에도 적용해 보았다.
  • 새롭게 문자열 처리 방법을 알게 되어서 좋은 공부가 된 것 같다.