[백준] 5052번 전화번호 목록 _ Java, Python

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

5052번: 전화번호 목록

 

 

---

 

1. Preview

시간 복잡도

   1) Trie 자료구조 : O(N * L)

        - N : 전화번호 개수

        - L : 전화번호 길이

 

   2) 문자열 비교 : O(N)

 

 

공간 복잡도 : O(N)

 

 

---

 

2. 초기 접근 방법

https://wch-0625.tistory.com/102

 

자바 Trie 자료구조 구현

 

 

---

 

3. 생각

자바로 문제를 풀고,

주로 사용하는 파이썬으로도 Trie 자료구조를 구현 연습을 위해서 다시금 풀어보았다.

 

 

파이썬으로 풀 때 2가지 방법으로 풀었는데 다음과 같다.

 

첫번째 방법

1. 입력받은 전화번호를 모두 Trie 에 insert() 한다.

2. 이후, 길이가 짧은 전화번호부터 search()를 진행하며 일관성 체크를 진행한다.

3. 마지막 노드의 children 유무에 따라서 일관성 체크가 결정된다.

def search(self, string):
    curr_node = self.head

    for s in string:
        if s in curr_node.children:
            curr_node = curr_node.children[s]

    # children이 남아있으면 전화번호가 겹치는 것을 의미한다.
    # 911, 9112 → NO
    if curr_node.children:
        return False

    # 남아있지 않으면 일관성 있는 독립적인 번호이다.
    # 911, 912 → YES
    else:
        return True

 

 

두번째 방법

1. 길이가 짧은 전화번호부터 search()를 진행하며 일관성 체크를 진행한다.

2. Trie에 없는 새로운 번호일 시 break를 하고, 해당 지점에서 리프 노드인지 체크를 한다.

3. 리프 노드일 경우 이전 번호가 겹치므로 일관성이 없는 번호이고,

               아닐 경우 일관성 있는 독립적인 번호이다.

def search(self, string):
    curr_node = self.head

    for s in string:
        if s in curr_node.children:
            curr_node = curr_node.children[s]
        else: # 존재하지 않는 s이면 break 이후, 리프노드인지 확인한다.
            break

    # curr_node가 리프노드인 것은 일관성이 없는 번호임을 의미한다.
    # 911, 9112 → NO
    if curr_node.isLeaf:
        return False

    # 남아있지 않으면 일관성 있는 독립적인 번호이다.
    # 911, 912 → YES
    else:
        return True

 

 

ps. 마지막 풀이처럼 문자열을 비교해서 전화번호의 일관성 여부를 파악할 수도 있다.

(접두사 문제 때는 접두사의 개수를 찾는 문제로, 위와 같은 접근 시 O(nC2) 시간복잡도로 시간초과가 났지만,

전화번호 문제의 경우는 일관성을 어긋난 번호의 개수를 구하는 것이 아니라, 유무만 판단하면 됐기에 정렬 후 i, i+1 번째가 일관성 있는지 비교하는 O(n) 시간복잡도로 빠르게 풀 수 있다.)

 

 

---

 

4. 코드

1) Java - Trie 자료구조

// 일관성 없는 전화번호 목록이라도, 일단 입력은 끝까지 받아야한다.
// "1234", "123" 처리만 하고 "123", "1234" 일 때의 처리는 하지 않았다.

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

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

class Trie {
    TrieNode rootNode;

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

    void insert(String word) {
        TrieNode node = this.rootNode;

        for (int i = 0; i < word.length(); ++i) {
            node = node.childNodes.computeIfAbsent(word.charAt(i), character -> new TrieNode());
        }

        node.isLeaf = true;
    }

    boolean search(String word) {
        TrieNode node = this.rootNode;

        for (int i = 0; i < word.length(); ++i) {
            node = node.childNodes.getOrDefault(word.charAt(i), null);

            // 중간에 값이 없을 때, 일관성이 있는 전화번호 목록일 때이다.
            // ex. "12340", "12341"
            if (node == null) {
                return true; // 일관성이 있다.
            }

            // 중간 노드가 리프노드로 존재할 시
            // ex. "1234", "123" → '3'일 때 걸림
            if (node.isLeaf) {
                return false; // 일관성이 없다.
            }
        }

        // word의 마지막 노드가 이전에 자식노드가 없을 시, 처음 삽입된 것이므로
        // ex. "123"
        if (node.childNodes.isEmpty()) {
            return true;
        }
        // ex. "123", "1234"
        return false;
    }
}

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

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

        for (int i = 0; i < T; ++i) {
            Trie trie = new Trie();
            boolean consistencyFlag = true;

            int N = Integer.parseInt(br.readLine());
            for (int j = 0; j < N; ++j) {
                String number = br.readLine();

                // 입력값은 일단 계속 받아야 한다.
                if (consistencyFlag == false) {
                    continue;
                }

                // 삽입하기 전에 Trie 자료구조에서 지금 number가 일관성 있는지 체크한다.
                boolean consistency = trie.search(number);

                // 일관성이 있다면 삽입해준다.
                if (consistency) {
                    trie.insert(number);
                }
                // 일관성이 없다면 이후 전화번호는 볼 필요가 없다.
                else {
                    consistencyFlag = false;
                }
            }

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

 

 

2) Python - Trie 자료구조(1)

# 참고 : https://alpyrithm.tistory.com/72
# https://m.blog.naver.com/cjsencks/221740232900
# https://velog.io/@cjkangme/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%8A%B8%EB%9D%BC%EC%9D%B4Trie-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

import sys
input = sys.stdin.readline

class TrieNode:
    def __init__(self, key, isLeaf=None):
        self.key = key
        self.isLeaf = isLeaf
        self.children = {}

class Trie:
    # Trie 헤드 노드 생성
    def __init__(self):
        self.head = TrieNode(None)


    # 시간복잡도 : O(N*len(str))
    def insert(self, string):
        # 트리 헤드
        curr_node = self.head

        for s in string:
            # 현재 노드에 해당하는 글자의 자식이 없다면 새로운 노드로 추가
            if s not in curr_node.children:
                curr_node.children[s] = TrieNode(s)

            # 다음 노드로 이동
            curr_node = curr_node.children[s]

        # 리프노드에 '전체 문자열' 저장
        curr_node.isLeaf = string


    # 시간복잡도 : O(len(str))
    def search(self, string):
        curr_node = self.head

        for s in string:
            if s in curr_node.children:
                curr_node = curr_node.children[s]

        # children이 남아있으면 전화번호가 겹치는 것을 의미한다.
        # 911, 9112 → NO
        if curr_node.children:
            return False

        # 남아있지 않으면 일관성 있는 독립적인 번호이다.
        # 911, 912 → YES
        else:
            return True



T = int(input().strip())
for _ in range(T):
    N = int(input())
    nums = []
    trie = Trie()
    flag = True

    for _ in range(N):
        num = input().strip()
        nums.append(num)
        trie.insert(num)

    # 길이가 짧은 전화번호부터 search를 진행한다.
        # 일관성 체크를 더 빠르게 하기 위함.
    nums.sort()
    for num in nums:
        if not trie.search(num):
            flag = False
            break

    if flag:
        print("YES")
    else:
        print("NO")

 

 

3) Python - Trie 자료구조(2)

import sys
input = sys.stdin.readline

class TrieNode:
    def __init__(self, key, isLeaf=None):
        self.key = key
        self.isLeaf = isLeaf
        self.children = {}

class Trie:
    # Trie 헤드 노드 생성
    def __init__(self):
        self.head = TrieNode(None)

    def insert(self, string):
        # 트리 헤드
        curr_node = self.head

        for s in string:
            # 현재 노드에 해당하는 글자의 자식이 없다면 새로운 노드로 추가
            if s not in curr_node.children:
                curr_node.children[s] = TrieNode(s)

            # 다음 노드로 이동
            curr_node = curr_node.children[s]

        # 리프노드에 '전체 문자열' 저장
        curr_node.isLeaf = string


    def search(self, string):
        curr_node = self.head

        for s in string:
            if s in curr_node.children:
                curr_node = curr_node.children[s]
            else: # 존재하지 않는 s이면 break 이후, 리프노드인지 확인한다.
                break

        # curr_node가 리프노드인 것은 일관성이 없는 번호임을 의미한다.
        # 911, 9112 → NO
        if curr_node.isLeaf:
            return False

        # 남아있지 않으면 일관성 있는 독립적인 번호이다.
        # 911, 912 → YES
        else:
            return True



T = int(input().strip())
for t in range(T):
    N = int(input())
    nums = []
    trie = Trie()
    flag = True

    for _ in range(N):
        num = input().strip()
        nums.append(num)

    # 길이가 짧은 전화번호부터 search를 진행한다.
        # 일관성 체크를 더 빠르게 하기 위함.
    nums.sort()
    for num in nums:
        # 일관성 없는 번호일 경우 break
        if not trie.search(num):
            flag = False
            break

        trie.insert(num)

    if flag:
        print("YES")
    else:
        print("NO")

 

 

4) Python - 문자열 비교

import sys
input = sys.stdin.readline

T = int(input().strip())
for t in range(T):
    N = int(input())
    nums = []
    flag = True

    for _ in range(N):
        num = input().strip()
        nums.append(num)

    nums.sort()

    for i in range(len(nums)-1):
        if nums[i] == nums[i+1][:len(nums[i])]:
            flag = False

    if flag:
        print("YES")
    else:
        print("NO")