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

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

 

내가 푼 틀린 풀이 - 시간초과

채점 결과

정확성: 83.3

효율성: 8.3

합계: 91.7 / 100.0

 

HashMap이랑 startWith()함수 같이 사용해서 풀고 싶었는데, 최악의 경우 100만 길이의 입력값이 들어와서 시간초과가 나온다.

해당 풀이는 모든 전화번호에 대한 접두사를 비교하기 위해 중첩된 반복문을 사용하고 있다.

외부 루프에서는 phone_book 배열을 순회하고 내부 루프에서는 다시 모든 전화번호를 순회하면서 현재 전화번호를 비교하고 있다. 이렇게 하면 시간 복잡도가 O(N^2)이 되어 많은 데이터에 대해서는 처리가 불가능하게 느려진다.

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        HashMap<String, String> map = new HashMap<>();
        for (String x : phone_book) {
            map.put(x, x);
            int cnt = 0;
            for (int i = 0; i < phone_book.length; i++) {
                if (map.get(x).startsWith(phone_book[i]) ) {
                    cnt++;
                    if (cnt >= 2) {
                        return false;
                    }
                }

            }
        }
        return answer;
    }
}

정확성 테스트

테스트 1 〉	통과 (0.07ms, 77.6MB)
테스트 2 〉	통과 (0.05ms, 80MB)
테스트 3 〉	통과 (0.28ms, 74.3MB)
테스트 4 〉	통과 (0.21ms, 76.9MB)
테스트 5 〉	통과 (0.09ms, 76.5MB)
테스트 6 〉	통과 (0.07ms, 74.3MB)
테스트 7 〉	통과 (0.09ms, 75.5MB)
테스트 8 〉	통과 (0.21ms, 76.2MB)
테스트 9 〉	통과 (0.22ms, 77.3MB)
테스트 10 〉	통과 (0.21ms, 76.6MB)
테스트 11 〉	통과 (0.09ms, 83.3MB)
테스트 12 〉	통과 (0.20ms, 73.9MB)
테스트 13 〉	통과 (0.07ms, 76.2MB)
테스트 14 〉	통과 (44.33ms, 87.7MB)
테스트 15 〉	통과 (39.04ms, 91.4MB)
테스트 16 〉	통과 (74.24ms, 84.7MB)
테스트 17 〉	통과 (109.98ms, 93.1MB)
테스트 18 〉	통과 (113.17ms, 95.4MB)
테스트 19 〉	통과 (53.39ms, 86.9MB)
테스트 20 〉	통과 (161.44ms, 90.8MB)

효율성 테스트

테스트 1 〉	통과 (0.18ms, 59.3MB)
테스트 2 〉	통과 (0.17ms, 57MB)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)

 

 

다른 사람 풀이 - HashMap, containsKey()사용, substring() 사용

나는 문제 풀이하려고 할때마다 substring()의 존재를 계속 잊어버린다, 문자열 문제에서 substirng함수 잊지말자! 

 

먼저, 모든 전화번호와 그 인덱스를 HashMap에 저장합니다. 여기서 value값에 저장한 인덱스는 쓸모 없습니다.

두 번째 반복문에서는 각 전화번호의 접두사를 검사할 때, HashMap을 사용하여 이미 저장된 번호 중 어떤 번호의 접두사로 시작하는지를 빠르게 확인합니다. 특히 두번째 반복문에서 인덱스에 해당하는 문자열의 길이를 순회하는게 인상적입니다.

이렇게 하면 중첩 반복문 없이도 모든 접두사를 검사할 수 있으므로 시간 복잡도가 훨씬 낮아집니다.
시간 복잡도는 O(N)으로 훨씬 효율적이며, 따라서 더 많은 데이터에 대해 성공적으로 작동할 것으로 예상됩니다.

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
        HashMap<String, Integer> map = new HashMap<>();

        // 전화번호를 HashMap에 저장
        for (int i = 0; i < phone_book.length; i++) {
            map.put(phone_book[i], i);
        }

        // 각 전화번호에 대해 모든 접두사를 확인
        for (int i = 0; i < phone_book.length; i++) {
            for (int j = 1; j < phone_book[i].length(); j++) {
                // 다른 전화번호의 접두사가 있는지 확인
                if (map.containsKey(phone_book[i].substring(0, j))) {
                    return false;
                }
            }
        }

        return true;
    }
}

정확성 테스트

테스트 1 〉	통과 (0.06ms, 69.8MB)
테스트 2 〉	통과 (0.07ms, 72.3MB)
테스트 3 〉	통과 (0.07ms, 77.4MB)
테스트 4 〉	통과 (0.09ms, 74.4MB)
테스트 5 〉	통과 (0.09ms, 75.3MB)
테스트 6 〉	통과 (0.07ms, 72.7MB)
테스트 7 〉	통과 (0.09ms, 76.5MB)
테스트 8 〉	통과 (0.08ms, 70.3MB)
테스트 9 〉	통과 (0.11ms, 73.5MB)
테스트 10 〉	통과 (0.08ms, 74.5MB)
테스트 11 〉	통과 (0.09ms, 74.5MB)
테스트 12 〉	통과 (0.08ms, 80.1MB)
테스트 13 〉	통과 (0.08ms, 84.6MB)
테스트 14 〉	통과 (3.61ms, 73.6MB)
테스트 15 〉	통과 (4.29ms, 75.5MB)
테스트 16 〉	통과 (7.48ms, 85MB)
테스트 17 〉	통과 (9.95ms, 69.4MB)
테스트 18 〉	통과 (7.18ms, 87.7MB)
테스트 19 〉	통과 (4.05ms, 82MB)
테스트 20 〉	통과 (9.72ms, 79.1MB)

효율성 테스트

테스트 1 〉	통과 (5.31ms, 57.2MB)
테스트 2 〉	통과 (3.76ms, 56.7MB)
테스트 3 〉	통과 (329.61ms, 225MB)
테스트 4 〉	통과 (208.10ms, 137MB)

다른 사람 풀이 - Arrays.sort(), startsWith()

사전식으로 정렬해서 앞 뒤 전화번호를 비교하고 접두사인지 체크하는 코드이다.

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

정확성 테스트

테스트 1 〉	통과 (0.45ms, 76.8MB)
테스트 2 〉	통과 (0.28ms, 78MB)
테스트 3 〉	통과 (0.23ms, 70.4MB)
테스트 4 〉	통과 (0.27ms, 79MB)
테스트 5 〉	통과 (0.26ms, 63.2MB)
테스트 6 〉	통과 (0.30ms, 70.6MB)
테스트 7 〉	통과 (0.27ms, 67.2MB)
테스트 8 〉	통과 (0.28ms, 78.8MB)
테스트 9 〉	통과 (0.28ms, 76.9MB)
테스트 10 〉	통과 (0.24ms, 78.3MB)
테스트 11 〉	통과 (0.23ms, 67.6MB)
테스트 12 〉	통과 (0.20ms, 66.3MB)
테스트 13 〉	통과 (0.27ms, 77MB)
테스트 14 〉	통과 (2.00ms, 75.4MB)
테스트 15 〉	통과 (4.53ms, 80.8MB)
테스트 16 〉	통과 (3.98ms, 76.1MB)
테스트 17 〉	통과 (4.54ms, 77.4MB)
테스트 18 〉	통과 (5.82ms, 85.7MB)
테스트 19 〉	통과 (3.78ms, 83.5MB)
테스트 20 〉	통과 (6.22ms, 81MB)

효율성 테스트

테스트 1 〉	통과 (18.30ms, 55.8MB)
테스트 2 〉	통과 (21.17ms, 56.4MB)
테스트 3 〉	통과 (347.17ms, 97.8MB)
테스트 4 〉	통과 (251.05ms, 96.7MB)