[프로그래머스 JAVA] 전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

 

전화번호 목록 문제를 다시 정리하면서, 왜 어떤 풀이는 통과하고 어떤 풀이는 일부 테스트에서 실패했는지를 단계적으로 정리해본다. 핵심은 접두사 관계를 한쪽 방향만 보지 않았는지 여부다.

 

문제 핵심
어떤 전화번호가 다른 전화번호의 접두사인 경우가 하나라도 있으면 false를 반환해야 한다. 여기서 중요한 점은 접두사 관계가 입력 순서와 무관하게 성립한다는 것이다. 짧은 번호가 먼저 나오든, 긴 번호가 먼저 나오든 모두 잡아내야 한다.

 

기존에 실패했던 접근의 한계
HashSet에 지금까지 등장한 번호만 넣고, 현재 번호의 prefix가 set에 있는지를 검사하는 방식은 이전 번호가 현재 번호의 접두사인 경우만 처리한다. 반대로 긴 번호가 먼저 나오고 짧은 번호가 나중에 나오는 경우는 놓치게 된다. 이 때문에 특정 테스트 케이스에서만 오답이 발생한다.

아래는 이 문제를 해결하는 대표적인 세 가지 풀이 방법이다.

 

1. 정렬 후 인접 비교
가장 많이 쓰이고, 구현도 가장 간단한 방식이다. 전화번호를 사전순으로 정렬하면 접두사 관계에 있는 문자열들은 반드시 서로 인접하게 된다. 따라서 현재 문자열과 다음 문자열만 비교하면 된다.

 

아이디어
정렬된 상태에서 phone_book[i+1]이 phone_book[i]로 시작하는지만 확인한다.

 

코드

import java.util.*;

class Solution {

    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);

        for (int i = 0; i < phone_book.length - 1; i++) {
            if (phone_book[i + 1].startsWith(phone_book[i])) {
                return false;
            }
        }
        return true;
    }
}

 

 

 

특징
구현이 짧고 실수할 여지가 적다. 실전 코딩테스트에서는 이 방식이 가장 현실적인 선택이다.

 

2. 해시맵을 이용한 prefix 검사
전체 전화번호를 먼저 저장해두고, 각 번호에 대해 자기 자신보다 짧은 모든 prefix가 존재하는지를 검사하는 방식이다. 입력 순서와 무관하게 항상 올바르게 동작한다.

 

아이디어
모든 번호를 HashMap에 넣은 뒤, 각 번호의 substring(0, j)가 map에 존재하는지 확인한다. j는 문자열 길이보다 작게만 사용하므로 자기 자신은 검사 대상이 아니다.

 

코드

import java.util.*;
class Solution {

    public boolean solution(String[] phone_book) {
        HashSet<String> set = new HashSet<>();
    
        for (int i = 0; i < phone_book.length; i++) {
            set.add(phone_book[i]);
        }
        
        for (int i = 0; i < phone_book.length; i++) {
            for(int j = 1; j < phone_book[i].length(); j++){
                if (set.contains(phone_book[i].substring(0, j))) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

 

 

특징
논리는 직관적이지만 substring 생성 비용 때문에 문자열 길이가 길어질수록 비효율적일 수 있다. 그래도 문제 조건 내에서는 충분히 통과 가능하다.

 

3. 트라이(Trie)
접두사 문제의 정석적인 자료구조다. 숫자를 한 자리씩 노드로 저장하며 내려가면서 접두사 충돌을 탐지한다.

 

아이디어
번호를 삽입하는 과정에서 두 가지 경우를 확인한다.
첫째, 내려가는 중 이미 어떤 번호가 끝난 지점이라면 그 번호가 접두사다.
둘째, 번호 삽입이 끝났는데 이미 자식 노드가 존재한다면 현재 번호가 다른 번호의 접두사다.

 

코드

class Solution {

    static class Node {
        Node[] next = new Node[10];
        boolean end;
    }

    public boolean solution(String[] phone_book) {
        Node root = new Node();

        for (String num : phone_book) {
            if (!insert(root, num)) return false;
        }
        return true;
    }

    private boolean insert(Node root, String num) {
        Node cur = root;

        for (int i = 0; i < num.length(); i++) {
            int d = num.charAt(i) - '0';

            if (cur.next[d] == null) {
                cur.next[d] = new Node();
            }
            cur = cur.next[d];

            if (cur.end) return false;
        }

        for (int i = 0; i < 10; i++) {
            if (cur.next[i] != null) return false;
        }

        cur.end = true;
        return true;
    }
}

 

 

특징
시간 복잡도는 가장 좋지만 구현 난이도가 높다. 이 문제 하나만 놓고 보면 과한 선택일 수 있고, 접두사 문제가 반복적으로 등장할 때 진가를 발휘한다.

 

마무리
이 문제에서 가장 중요한 교훈은 접두사 검사를 한 방향만 보면 안 된다는 점이다. 정렬 풀이를 자연스럽게 떠올릴 수 있다면 이미 문제의 본질을 이해한 상태다. 해시맵 풀이는 개념을 명확히 이해하는 데 도움이 되고, 트라이는 접두사 문제 전반을 관통하는 자료구조로 기억해두면 충분하다.