[프로그래머스] 전화번호 목록 - Java

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

프로그래머스

 

⭐️ 중요 포인트

1. 각 단어의 접두사와 중복되는 단어가 있는지 확인하기 위해 HashSet을 사용

(몇 번 중복되었는지와 같은 빈도 수는 필요없기 때문에 HashMap 대신 HashSet을 사용)

2. 전화번호를 HashSet에 먼저 저장 -> 이 부분이 가장 문제였음

(사실 시간복잡도 측면으로 봤을 때는 동일함. [전화번호의 개수 : N / 각 길이 : L 이라고 가정]

(1) 접두사를 먼저 HashSet에 저장하고 전화번호를 비교하는 것 : O(N * L) + O(N)

(2) 전화번호를 먼저 HashSet에 저장하고 접두사를 비교하는 것 : O(N) + O(N * L)

그러나 실제로 돌려보면 (1)번 방법에서는 HashSet에 더 많은 String이 들어가게 되고, 이는 경우에 따라 Hash Collision으로 이어질 수 있음. 즉, 시간복잡도는 같지만 Hash의 특성상 (2)번 방법이 더 유리) -> 아래 두 번째 코드가 시간초과 코드

3. 각 전화번호의 접두사들을 확인하며 Hash에 들어있는 전화번호와 겹치는지 확인

 

🔥 Hash를 사용할 때는 동일한 시간복잡도라도 다른 방법일 경우 Hash에 더 적은 값을 넣는 방법을 선택하는 것이 유리함.

 

 

import java.util.*;

class Solution {
    
    static String[] static_phone_book;
    static Set<String> hashSet;
    
    static void init(String[] phone_book) {
        static_phone_book = phone_book;
        hashSet = new HashSet<>();
    
    }
    
    static boolean solve() {
        // 전화번호를 hashSet에 저장
        for (int i = 0; i < static_phone_book.length; i++) {
            hashSet.add(static_phone_book[i]);
        }
        
        // 각 전화번호의 접두사(start <= substring < end)까지 돌며 각 단어들의 접두사와 같은 전화번호가 있는지 확인
        for (int i = 0; i < static_phone_book.length; i++) {
            for (int j = 0; j < static_phone_book[i].length(); j++) {
                if (hashSet.contains(static_phone_book[i].substring(0, j))) {
                    return false;
                }
            }
        }
        return true;
    }
    
    public boolean solution(String[] phone_book) {
        init(phone_book);
        
        return solve();
    }
}

 

(틀린 코드 - 시간초과) -> 접두사를 HashSet에 먼저 넣고 비교하는 방법

(HashSet에 너무 많은 값이 들어가서 Hash Collision이 발생하여 시간초과가 나는 것으로 추측)

import java.util.*;

class Solution {
    
    static String[] static_phone_book;
    static Set<String> hashSet;
    
    static void init(String[] phone_book) {
        static_phone_book = phone_book;
        hashSet = new HashSet<>();
    
    }
    
    static boolean solve() {
        // 각 전화번호의 접두사(start <= substring < end)까지 돌며 각 단어들의 접두사와 같은 전화번호가 있는지 확인
        for (int i = 0; i < static_phone_book.length; i++) {
            for (int j = 0; j < static_phone_book[i].length(); j++) {
                hashSet.add(static_phone_book[i].substring(0, j));
            }
        }
        
        // 전화번호를 hashSet에 저장
        for (int i = 0; i < static_phone_book.length; i++) {
            if (hashSet.contains(static_phone_book[i])) {
                return false;
            }
        }
        

        return true;
    }
    
    public boolean solution(String[] phone_book) {
        init(phone_book);
        
        return solve();
    }
}