[프로그래머스/Java] Lv.2 - 전화번호 목록

📝 문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하는 문제입니다. 접두어인 경우가 있으면 false를, 그렇지 않으면 true를 반환해야 합니다.

• 제한 사항: 전화번호부의 길이는 최대 1,000,000입니다. ($O(N^2)$ 풀이는 불가능합니다.)

---

💡 접근 방식

1. 정렬(Sorting)의 도입

처음에는 단순히 HashSet에 번호를 넣으며 확인했지만, ["112", "11"]과 같이 긴 번호가 짧은 번호보다 먼저 등장할 경우 접두어를 찾아내지 못하는 문제가 있었습니다.
이를 해결하기 위해 Arrays.sort()를 사용했습니다. 문자열 정렬을 수행하면 길이가 짧거나 사전순으로 앞선 번호가 먼저 오기 때문에, 접두어가 뒤에 오는 경우를 방지할 수 있습니다.

2. 해시(Hash)를 통한 효율적인 탐색

각 전화번호를 한 글자씩 StringBuilder로 붙여가며, 현재까지 만들어진 부분 문자열이 HashSet에 존재하는지 확인합니다.

• contains() 연산은 평균적으로 $O(1)$의 시간 복잡도를 가지므로, 전체 전화번호를 한 번만 순회($O(N)$)하면 문제를 해결할 수 있습니다.
• 부분 문자열이 존재한다면 즉시 false를 반환하여 효율성을 높였습니다.

---

💻 구현 코드

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        Arrays.sort(phone_book);
        Set<String> set = new HashSet<>();
        
        for(String num : phone_book) {
            StringBuilder st = new StringBuilder();
            for(int i=0; i<num.length(); i++) {
                st.append(num.charAt(i));
                if(set.contains(st.toString())) {
                    System.out.println(st);
                    return false;
                }
            }
            set.add(num);
        }
        
        return answer;
    }
}

---

✨ 느낀 점

✅ 정렬의 마법

• 단순히 데이터를 쌓는 것보다, 데이터를 정렬하여 순서를 제어하는 것이 로직의 복잡도를 얼마나 낮출 수 있는지 배웠습니다. 정렬 덕분에 두 번의 루프를 돌 필요 없이 단방향 탐색만으로 예외 케이스(112, 11)를 처리할 수 있었습니다.

✅ 도구의 조합

• StringBuilder를 활용한 동적 문자열 생성과 HashSet의 빠른 탐색 속도를 조합하여 대량의 데이터(100만 건)를 처리하는 최적의 방법을 고민해 볼 수 있었습니다.

✅ 트러블슈팅의 가치

• 첫 번째 시도에서의 실패(순서 문제 -> 예) {"112", "11"})를 분석하고, 이를 해결하기 위해 정렬을 도입하거나 탐색 방향을 바꿨던 고민의 과정이 실력 향상에 큰 도움이 되었습니다. 라이브러리 함수 하나가 알고리즘의 전체 흐름을 바꿀 수 있다는 점이 흥미로웠습니다.