[프로그래머스] 알고리즘 고득점 Kit - 해시 | Lv2 전화번호목록

🔍 문제 보러 가기

문제 설명

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 리턴하는 문제

접근 방법

1. 전화번호를 정렬한다.
2. 인접한 전화번호끼리 접두사 여부를 확인한다.
3. 접두사가 있으면 false을 반환한다.

내 코드

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        HashSet<String> set = new HashSet<>();
        
        for(String p : phone_book) {
            set.add(p);
        }
        
        for(String s : set) {
            for (String str : set) {
                if (!s.equals(str) && str.length() > s.length()) {
                    if(s.equals(str.substring(0, s.length()))) {
                        return false;
                    }
                }
            }
        }
        
        return true;
    }
}

-> 효율성 테스트 실패함

개선된 코드

import java.util.HashSet;

class Solution {
    public boolean solution(String[] phone_book) {
        // 1. 전화번호를 정렬
        Arrays.sort(phone_book);

        // 2. 인접한 전화번호끼리 접두사 여부를 확인
        for (int i = 0; i < phone_book.length - 1; i++) {
            // 현재 번호가 다음 번호의 접두사인지를 확인
            if (phone_book[i + 1].startsWith(phone_book[i])) {
                return false; // 접두사가 있으면 false 반환
            }
        }

        return true; // 접두사가 없으면 true 반환
    }
}

point

1. 정렬을 이용

• 이중 for문을 사용하면 시간 초과로 효율성 테스트에서 실패가 발생한다.

  • 이중 for문은 시간 복잡도가 O(n^2)로 증가해서 대규모 데이터에선 성능 문제가 생길 수 있다.

• 전화번호를 먼저 정렬한 후, 인접한 번호들만 비교하면 접두사를 확인하는데 충분하다.

• 정렬 후 인접한 번호끼리만 비교하면 O(n log n)으로 성능을 개선할 수 있다.

  • 정렬에 O(n log n), 인접한 번호를 비교하는 데 O(n)이 걸리므로 시간 복잡도는 O(n log n)이 된다. 이중 for문을 쓰는 O(n^2) 방식보다 훨씬 효율적이다.

참고 - 시간 복잡도

1. 정렬의 시간 복잡도: O(n log n)
   • 정렬을 수행하는 데 필요한 시간은 n log n이다. 여기서 n은 배열의 크기(전화번호의 개수)를 의미한다.
   • Java의 Arrays.sort() 메서드는 Timsort 알고리즘을 사용해 평균적으로 O(n log n)의 시간 복잡도를 가진다.
   • 정렬을 하는 과정에서 각 원소들을 비교하고, 그 위치를 정리하는 데 필요한 시간이 n log n이 되는 것이고, 이건 대부분의 효율적인 정렬 알고리즘(예: Merge Sort, Quick Sort 등)에서 발생하는 시간 복잡도이다.
2. 인접한 번호 비교의 시간 복잡도: O(n)
   • 정렬된 배열에서 인접한 전화번호들끼리만 접두사 관계인지 비교하면 된다.
   • 정렬된 배열에서는 한 번호와 그 다음 번호만 비교하면 충분하므로, 전체적으로 n - 1번의 비교만 필요하다.
   • 각 비교는 상수 시간(O(1))에 처리되므로, 이 과정을 모두 합치면 시간 복잡도는 O(n)이 된다.
3. 최종 시간 복잡도: O(n log n)
   • 정렬하는 데 O(n log n)의 시간이 걸리고, 그 후에 인접한 번호를 비교하는 데 O(n)이 추가된다.
   • 전체 시간 복잡도는 O(n log n + n)이지만, 시간 복잡도를 계산할 때는 더 큰 값만 고려하므로 최종적으로 O(n log n)이 된다.
4. 왜 이중 for문은 O(n^2)인가?

• 이중 for문은 모든 전화번호를 다른 모든 전화번호와 비교하는 방식이다. 첫 번째 for문이 n번 돌고, 그 안에서 두 번째 for문도 n번 돈다면, 총 비교 횟수는 n * n, 즉 O(n^2)이 된다.
• 예를 들어, 10개의 전화번호가 있다면, 이중 for문은 총 100번(10 * 10) 비교하지만, 정렬 후 인접 비교는 9번만 하면 된다.

5. 간단한 비교

• 정렬 + 인접 비교 (O(n log n)): 100만 개의 전화번호가 있으면 n log n은 약 2천만 회 연산이 발생.
• 이중 for문 (O(n^2)): 100만 개의 전화번호가 있으면 n^2은 10억 회 연산이 발생.