전화번호 목록_복습

2026.07.26

문제 풀이

1차 실행 오류

---

79.2/100

실패 및 시간 초과

---

실패 원인 분석

123, 12 순서의 배열에서
12는 123으로 시작하지 않지만, 123은 12로 시작하는 경우를 고려하지 않음

---

class Solution {
    public boolean solution(String[] phone_book) {
        for (int i = 0; i < phone_book.length; i++) {
            for (int j = i + 1; j < phone_book.length; j++) {
                if (phone_book[j].startsWith(phone_book[i])) {
                    return false;
                }
            }
        }
        return true;
    }
}

2차 실행 오류

---

91.7/100

시간 초과

---

시간 초과 원인 분석

1 <= phone_book <= 1,000,000 이므로 2중 for문을 사용하면 안됨

---

class Solution {
    public boolean solution(String[] phone_book) {
        if (phone_book.length <= 1) {
            return true;
        }
        
        for (int i = 0; i < phone_book.length; i++) {
            for (int j = 0; j < phone_book.length; j++) {
                if (i == j) {
                    continue;
                }
                if (phone_book[j].startsWith(phone_book[i])) {
                    return false;
                }
            }
        }
        return true;
    }
}

나의 코드

---

소요 시간: 31분
시간 복잡도: $O(n log n)$

---

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        
        if (phone_book.length <= 1) {
            return true;
        }
        
        for (int i = 1; i < phone_book.length; i++) {
            if (phone_book[i].startsWith(phone_book[i - 1]) || 
                phone_book[i - 1].startsWith(phone_book[i])) {
                return false;
            }
        }
        return true;
    }
}

AI 코드

---

시간 복잡도: $O(n)$

---

코드 분석

HashSet의 .contains()의 조회 속도가 $O(1)$이라는 점을 이용하여 해결

---

import java.util.HashSet;

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

        for (String number : phone_book) {
            for (int i = 1; i < number.length(); i++) {
                if (set.contains(number.substring(0, i))) {
                    return false;
                }
            }
        }
        return true;
    }
}

문제 풀이 후기

substring()과 contains()의 혼합 사용은 생각하지 못했다.
Hash의 활용 방법은 무궁무진 하다는 생각이 들었다.

이전에 해결하지 못했던 시간 초과 오류를 AI를 활용하지 않고
스스로 원인 분석 및 해결했다는 점에서 높은 점수를 주고 싶다.