프로그래머스 - 전화번호 목록 (JAVA)

프로그래머스 전화번호 목록 풀이 과정
약 1년 전에도 한 번 풀었던 문제다. 그때도 꽤 헤맸는데... 다시 풀어보니 또 헤맸다.
총 9번의 제출... 여전히 부족하다

---

1트 (오답)

→ 배열 요소 중 가장 짧은 길이를 기준으로, 슬라이딩 윈도우처럼 모든 부분 문자열을 Map에 저장한다.
→ 동일한 부분 문자열이 2개 이상 등장하면, 접두어 관계가 존재한다고 간주한다.

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        // 배열 요소 최소 길이 구하기
        int min_len = Integer.MAX_VALUE;
        for(String num : phone_book) min_len = Math.min(min_len, num.length());

        // 최소 길이로 나올 수 있는 모든 경우 맵에 저장
        Map<String, Integer> map = new HashMap<>();
        for(String num : phone_book) {
            for(int i=0; i<=num.length()-min_len; i++) {
                String str = num.substring(i, i+min_len);
                map.put(str, map.getOrDefault(str,0)+1);
            }
        }

        // 1보다 큰 경우 접두어가 있는걸로 간주
        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            if(entry.getValue() > 1) return false;
        }

        return true;
    }
}

위 풀이의 결과

• 접두어 관계는 반드시 앞에서부터 시작해야 하는데, 중간 인덱스(i)부터 시작하는 부분 문자열까지 전부 비교하고 있어 잘못된 접근이다.
• 예를 들어 "123"과 "312"가 있다면, 슬라이딩으로 "23", "31", "12" 등이 겹쳐 접두어가 없는데도 false를 리턴하는 오탐이 발생한다.
• 히스토리 기준으로 0점, 66.7점 구간에 해당하는 풀이다.

---

2트 (오답)

→ 슬라이딩이 문제였으니, 시작 인덱스를 0으로 고정한다.
→ 각 번호의 앞 min_len 글자만 잘라서 Map에 저장하면, 최소 길이 번호가 다른 번호의 접두어인 경우를 잡을 수 있지 않을까?

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        // 배열 요소 최소 길이 구하기
        int min_len = Integer.MAX_VALUE;
        for(String num : phone_book) min_len = Math.min(min_len, num.length());

        // 최소 길이로 나올 수 있는 모든 경우 맵에 저장
        Map<String, Integer> map = new HashMap<>();
        for(String num : phone_book) {
            String str = num.substring(0, min_len);
            map.put(str, map.getOrDefault(str,0)+1);
        }

        // 1보다 큰 경우 접두어가 있는걸로 간주
        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            if(entry.getValue() > 1) return false;
        }

        return true;
    }
}

위 풀이의 결과

• 최소 길이 번호가 접두어인 케이스는 어느 정도 잡히지만, 여전히 길이가 다른 번호들 사이의 접두어 관계를 전부 처리하지 못한다.
• 예를 들어 "12"와 "123"은 잡히지만, 접두어 관계 없이 앞 두 글자가 우연히 같은 번호들끼리 오탐이 생긴다.
• 히스토리 기준으로 54.2점, 79.2점, 91.7점 구간을 오가던 풀이의 원인이다.

---

3트 (정답)

→ 발상을 바꾸자. 모든 번호를 Map에 넣어두고, 각 번호의 모든 접두어(prefix) 를 직접 잘라서 Map에 존재하는지 확인하자.
→ 어떤 번호의 접두어가 Map에 존재한다면, 그게 곧 다른 번호와의 접두어 관계를 의미한다.
(솔직히 이 방향은 AI의 도움을 받아서 풀었던 나의 과거 풀이를 참고했다...)

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Map<String, Integer> map = new HashMap<>();
        for(String num : phone_book) {
            map.put(num, map.getOrDefault(num,0)+1);
        }

        for(String num : phone_book) {
            for(int j=0; j<num.length(); j++) {
                if(map.containsKey(num.substring(0,j))) {
                    return false;
                }
            }
        }

        return true;
    }
}

위 풀이의 결과

• 정확성과 효율성 테스트 드뎌 통과
• 히스토리상 2025-06-12, 2026-04-21 두 번 모두 이 방향으로 결국 통과했다.
• 다만 Map<String, Integer>을 쓰고 있는데, 이 풀이에서 Value(Integer)는 전혀 활용되지 않는다.
• Key의 존재 여부만 확인하면 되므로, Map보다 Set이 더 적합한 자료구조다.

---

4트 (리팩토링)

→ Map 대신 Set을 사용해 불필요한 Value 관리를 제거하자.
→ 코드가 더 간결해지고, 의도도 명확해진다.

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Set<String> set = new HashSet<>();
        for(String num : phone_book) {
            set.add(num);
        }

        for(String num : phone_book) {
            for(int j=0; j<num.length(); j++) {
                if(set.contains(num.substring(0,j))) {
                    return false;
                }
            }
        }

        return true;
    }
}

위 풀이의 결과

• Map → Set으로 교체하면서 코드가 훨씬 간결해졌다.
• contains() 하나로 접두어 존재 여부를 O(1)에 확인할 수 있어 가독성과 효율 모두 개선됐다.
• 최종 제출 겨우 통과~

---

1년 전에 한 번 풀었던 문제인데도 다시 같은 구간에서 헤맸다. 그때의 나도, 지금의 나도 슬라이딩 윈도우 방향으로 먼저 손이 갔다는 게 신기하면서도 조금 부끄럽다. 핵심은 "모든 접두어를 직접 잘라서 Set에서 탐색한다" 는 단순한 발상이었는데, 앞으로는 이 패턴을 더 빠르게 떠올릴 수 있도록 많이 풀어봐야겠다.