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

• 프로그래머스 문제 URL

전화번호 목록에서 접두어 문제 해결
주어진 전화번호 목록에서 한 번호가 다른 번호의 접두어인 경우가 있는지 확인함.

---

문제 접근

• 입력
  phone_book: 전화번호 문자열 배열 (1 ≤ 길이 ≤ 1,000,000)
  각 번호 길이: 1 ≤ 20자리

  예를 들어,

  ["119", "97674223", "1195524421"]

  → "119"가 "1195524421"의 접두어 → false

• 출력
  접두어가 있으면 false, 없으면 true.

---

제출 실패 코드 & 로그

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        // 문자열의 접두어2자를 set으로 담아서 배열의 길이와 set의 size가 다르면 false, 같으면 true
        Set<String> num_start = new HashSet<>();
        for (String a : phone_book) {
            num_start.add(a.substring(0, 2));
        }
        if (phone_book.length != num_start.size()) {
            answer = false;
        }
        return answer;
    }
}

실패 로그:

테스트 1 〉	실패 (0.00ms)
테스트 2 〉	실패 (0.01ms)
테스트 3 〉	실패 (0.00ms)
테스트 4 〉	실패 (0.01ms)
테스트 5 〉	실패 (0.00ms)
테스트 6 〉	실패 (0.00ms)
테스트 7 〉	실패 (0.01ms)
테스트 8 〉	실패 (0.00ms)
테스트 9 〉	실패 (0.00ms)
테스트 10 〉	실패 (0.01ms)

실패 원인:
"123", "124" → 앞 2자리 같아도 접두어 아님 → 고정 2자리로는 불가능!

---

정답 제출 코드

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        // 1. 전화번호 정렬
        Arrays.sort(phone_book);
        
        // 2. 인접한 쌍만 접두어 확인 (정렬 후 효율적)
        for (int i = 0; i < phone_book.length - 1; i++) {
            String current = phone_book[i];
            String next = phone_book[i + 1];
            
            // current가 next의 접두어인지 확인
            if (next.startsWith(current)) {
                return false;
            }
        }
        return true;
    }
}

---

핵심 개념

1. 정렬 + 인접 비교 최적화

   정렬 전: ["119", "97674223", "1195524421"]
   정렬 후: ["119", "1195524421", "97674223"]
   → "119"와 "1195524421" 인접 → 바로 접두어 발견!

2. startsWith() 활용

   next.startsWith(current) → current가 next의 접두어?
   "1195524421".startsWith("119") → true

3. 시간복잡도

   • 정렬: O(n log n)
   • 비교: O(n × 번호길이)
   • 총 O(n log n) — n=10^6 통과.

---

출력 예시

입력	출력	설명
["119", "97674223", "1195524421"]	false	"119"가 접두어
["123", "456", "789"]	true	접두어 없음
["12", "123"]	false	"12"가 접두어

---

실패 원인 분석 & 해결

❌ 실패 접근	✅ 정답 접근	이유
고정 2자리 substring(0,2)	전체 길이 startsWith()	번호 길이 다양 (1~20자리)
HashSet으로 중복 체크	정렬 후 인접 비교	앞자리 같아도 접두어 아님
O(n²) 가능성	O(n log n)	n=10^6에서 시간초과

핵심: "문자열 A가 B의 처음부터 시작하는가?" → startsWith() + 정렬!

---

정리

• 문자열 접두어 패턴 문제
• 정렬 → 인접 startsWith() 확인이 정석
• 고정 길이 자르기 절대 금지! 번호 길이 다양함