[프로그래머스]전화번호 목록 - 해쉬 + 아이디어

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

프로그래머스

 

 

 

내가 처음에 생각한 코드는 이중루프를 통해 O(N^2)의 시간복잡도를 가지고 있습니다.

phonebook의 길이가 백만개인데 이중루프를 사용하므로 1000000 * 1000000 = 1000000000000 (1조) 가 걸립니다.

 

 

 

IndexOf를 사용하여 간단히 풀어본 코드입니다.

효율성 테스트3, 4에서 시간초과가 납니다.

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        for(int i=0;i<phone_book.length;i++){
            String standard = phone_book[i];
            for(int j=0;j<phone_book.length;j++){
                if(i == j ) continue;
                if(standard.length() > phone_book[j].length() ) continue;
                if( phone_book[j].indexOf(standard) == 0){
                    System.out.println(standard);
                    System.out.println(phone_book[j]);
                    return false;
                }
            }
        }
        
        return answer;
    }
}

 

IndexOf 대신 StartsWith 라는 함수를 사용한 코드입니다. 이 코드 또한 시간초과가 납니다.

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);
        for(int i=0;i<phone_book.length;i++){
            String standard = phone_book[i];
            for(int j=0;j<phone_book.length;j++){
                if(i == j ) continue;
                if(standard.length() > phone_book[j].length() ) continue;
                if( phone_book[j].startsWith(standard) == true){
                // if( phone_book[j].indexOf(standard) == 0){
                    // System.out.println(standard);
                    // System.out.println(phone_book[j]);
                    return false;
                }
            }
        }
        
        return answer;
    }
}

 

 

HashMap을 사용할경우 시간이 훨씬 줄어듭니다.

HashMap이 엄청나게 차이가 큰 것 같습니다. 속도의 경우 Hashing이 훨씬 빠르다고 느꼈습니다.

여기서 내가 헷갈렸던점은 119의 접두어는 119는 될 수 없다.
숫자가 아예 같을경우는 접두어가 될 수 없다.

접두어의 의미가 헷갈렸습니다.

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        
        //1. HashMap을 만든다.
        HashMap<String, Integer> hashmap = new HashMap<>();
        for(int i=0;i<phone_book.length;i++){
            hashmap.put(phone_book[i], 1);
        }
        
        //2. 모든 전화번호의 접두어가 HashMap에 있는지 확인한다.
        for(int i=0;i<phone_book.length;i++){
            
            //여기서 내가 헷갈렸던점은 119의 접두어는 119는 될 수 없다.
            //숫자가 아예 같을경우는 접두어가 될 수 없다.
            for(int j=1; j<phone_book[i].length();j++){
                //길이를 1, 2, 3, 4 이렇게 접두어의 길이를 늘려가며 검사.
                if(hashmap.containsKey(phone_book[i].substring(0, j))){
                    return false;
                }
            }
        }
        
        return true;
    }
}

 

(https://www.youtube.com/watch?v=ggoKE9FQIEQ)

Sorting을 해서도 해결할 수 있습니다.

예시를 들어보ㅛ면

전화번호를 오름차순으로 정렬합니다.

0            1               2

12          6               6789

 

이렇게 오름차순으로 정렬햇기 때문에 

항상 앞의 숫자가 접두어가 될 수 밖에 없습니다. 

이렇게 푸는것보다는 hash가 나을 것 같습니다.

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phoneBook) {
        // 1. phoneBook을 sorting한다.
        Arrays.sort(phoneBook);

        // 2. 1중 Loop을 돌며 앞 번호가 뒷 번호의 접두어인지 확인한다.
        for (int i = 0; i < phoneBook.length - 1; i++)
            if (phoneBook[i + 1].startsWith(phoneBook[i]))
                return false;
        
        // 3. 여기까지 오면 접두어가 없다는 것이다.
        return true;
    }
}