[코딩테스트] Java 전화번호 목록

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

트라이 노드를 사용해서 문제를 풀었습니다. String에서 한자를 노드의 value로 생각하셔 문자가 같으면 자식 노드로 진입하면서 접두어가 같은지 확인합니다. 같지 않으면 접두어가 같지 않습니다.

 

이전에 문제를 풀었을 때 O(N^2)의 코드로 풀어서 좋은 방법이 없을까 하다가 트라이 노드로 문제를 풀었습니다. 하지만 코딩 테스트를 진행할 때에는 적합한 풀이는 아니라고 생각합니다.

폰켓몬 소스코드

import java.util.*;

class Solution {
    
    static class PhoneBook {
        // 트라이 노드 클래스 정의
        static class TrieNode {
            Map<Character, TrieNode> children = new HashMap<>();
            boolean isEndOfNumber;
        }

        // 루트 노드
        private TrieNode root = new TrieNode();

        // 번호를 트라이에 삽입
        private boolean insert(String number) {
            TrieNode current = root;
            for (char c : number.toCharArray()) {
                current.children.putIfAbsent(c, new TrieNode());
                current = current.children.get(c);

                // 번호의 중간에서 이미 끝인 경우 접두어 조건 위반
                if (current.isEndOfNumber) {
                    return false;
                }
            }

            // 번호가 완전히 끝난 경우를 표시
            current.isEndOfNumber = true;

            // 현재 노드에 자식이 있는 경우 접두어 조건 위반
            return current.children.isEmpty();
        }

        public boolean isConsistent(String[] phoneBook) {
            for (String number : phoneBook) {
                if (!insert(number)) {
                    return false;
                }
            }
            return true;
        }
    }
    
    public boolean solution(String[] phone_book) {
        PhoneBook phoneBookChecker = new PhoneBook();
        return phoneBookChecker.isConsistent(phone_book);
    }
}

코드 설명

 

• TrieNode 클래스: 각 문자를 자식으로 연결하는 트라이 노드입니다.
• insert 메서드: 전화번호를 트라이에 삽입하고 접두어 조건을 위반하는지 확인합니다. 중간에 이미 끝인 번호가 있거나 새로 추가된 번호의 마지막 노드에 자식이 있으면 false를 반환하여 접두어 조건 위반을 나타냅니다.
• isConsistent 메서드: 전화번호 목록의 각 번호를 insert 메서드로 확인하여 접두어 관계가 있는 경우 false를 반환합니다.