Programmers | Level 2 | 전화번호 목록

Jun 27, 2024

Published byJynn

999

Programmers | Level 2 | 전화번호 목록

Problems

📘 Src: Programmers
🗂️ Cat: Hash Table

Description

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 예를 들어, 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

이름	전화번호
구조대	119
박준영	97 674 223
지영석	11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book이 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false, 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

Constraints

phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
같은 전화번호가 중복해서 들어있지 않습니다.

Examples

phone_book	return
["119", "97674223", "1195524421"]	false
["123", "456", "789"]	true
["12", "123", "1235", "567", "88"]	false

Explanation

Example 1: "119"는 "1195524421"의 접두사이므로 false를 반환합니다.
Example 2: 어떤 번호도 다른 번호의 접두어가 아니므로 true를 반환합니다.
Example 3: "12"는 "123"의 접두사이므로 false를 반환합니다.

Solutions

⏳ TC: O(n log n)
💾 SC: O(1)

Solution.java

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;
    }
}

Approaches

이 문제를 해결하기 위해 해시 테이블을 사용하여 각 전화번호를 저장하고, 다른 전화번호의 접두어인지 확인하는 방식으로 접근할 수 있습니다. 그러나 더 효율적인 방법은 전화번호 배열을 정렬한 다음, 인접한 번호들만 비교하여 접두어인지 확인하는 것입니다. 이는 다음과 같은 단계로 진행됩니다:

전화번호 배열 정렬:
- 주어진 phone_book 배열을 정렬합니다.
- 정렬하면 접두어가 될 가능성이 있는 번호들이 인접하게 됩니다.
인접한 번호 비교:
- 정렬된 배열에서 인접한 두 번호를 비교하여 하나가 다른 하나의 접두어인지 확인합니다.
- 예를 들어, "12", "123", "1235"로 정렬된 배열에서 "12"는 "123"의 접두어입니다.
접두어 여부 반환:
- 인접한 두 번호 중 하나가 다른 하나의 접두어인 경우 false를 반환합니다.
- 그렇지 않은 경우, 모든 비교가 끝난 후 true를 반환합니다.

이 알고리즘은 정렬 단계에서 O(n log n)의 시간 복잡도를 가지며, 인접한 번호를 비교하는 단계에서 O(n)의 시간 복잡도를 가집니다. 최종적으로, 시간 복잡도는 O(n log n + n)이 되어 효율적인 해결 방법이 됩니다.

Attempts

String[] 배열을 정렬하면 사전순으로 정렬된다는 것을 떠올리지 못해서, 처음에는 전화번호 목록에서 접두어를 효율적으로 찾기 위해 해시 테이블을 사용하여 문제를 해결하려고 했습니다.

이를 위해, 전화번호를 길이 순으로 정렬한 다음 가장 짧은 전화번호의 길이를 해시 키의 길이로 설정하고, 각 전화번호를 순회하며 이 길이만큼의 해시 키를 생성하여 해시 테이블에 동일한 접두어를 가진 번호들을 그룹화한 후 저장했습니다. 이를 통해 각 그룹 내에서 접두어 관계를 확인하는 방식으로 접근했습니다:

Solution.java

import java.util.*;

class Solution {
    public boolean solution(String[] phoneBook) {
        // 전화번호를 길이 순으로 정렬
        Arrays.sort(phoneBook, (a, b) -> a.length() - b.length());
        int keySize = phoneBook[0].length();
        
        // 해시 테이블에 전화번호를 저장
        Map<String, List<String>> map = new HashMap<>();
        for (String phone : phoneBook) {
            String key = hash(phone, keySize);
            List<String> numbers = map.getOrDefault(key, new ArrayList<String>());
            numbers.add(phone);
            map.put(key, numbers);
        }
        
        // 각 그룹 내에서 접두어 관계 확인
        for (int i = 0; i < phoneBook.length; i++) {
            String key = hash(phoneBook[i], keySize);
            List<String> numbers = map.get(key);
            for (String number : numbers) {
                if (number.equals(phoneBook[i])) continue;        
                if (number.startsWith(phoneBook[i])) return false;
            }
        }
        
        return true;
    }
    
    private String hash(String phone, int keySize) {
        return phone.substring(0, keySize);
    }
}

이 접근 방식에서 두 가지 주요 실수가 있었습니다.

첫째, 접두어를 비교하기 위해 불필요하게 전화번호를 직접 비교하는 과정이 있었습니다. 이는 비효율적이며 코드의 복잡성을 증가시켰습니다.
둘째, 전화번호를 길이 순으로 정렬하고 해시 테이블을 사용한 접근 방식은 정렬된 배열을 사용한 간단한 해결책에 비해 더 복잡하고 비효율적이었습니다

이 코드의 시간 복잡도는 O(n log n)으로 효율적이지만, 공간 복잡도는 O(n)이고 불필요하게 복잡한 코드이므로 정렬된 배열을 사용한 간단한 해결책이 더 효율적입니다.

Algorithm
Hash Table