프로그래머스_전화번호목록_42577

문제 링크

조건

• phone_book : 전화번호 목록, string배열 길이 1~1000000
• 각 전화번호 길이 1~20 이하

 

접근 방법

1. 일반 정렬 후 탐색
   • Arrays.sort()로 문자열 오름차순 정렬
   • i+1번째 번호의 접두사가 i인지 확인
   • O(NlogN) + O(N) : 정렬 + 전체 탐색
   • 정확성 시간 0.15~0.3ms / 효율성 시간 17~20ms
2. 해시 사용
   • HashMap 사용해서 접두사 저장 => 데이터 탐색 시 O(1) 시간복잡도
   • map 길이만큼 중첩for문으로 i번째 번호가 나머지 번호와 접두사 관계에 있는지 확인
   • 정확성 시간 0.03~0.05ms / 효율성 시간 3ms

※ Hash ※

Hash의 경우 hash function을 이용해 데이터마다 고유의 hash code를 만들고, 이 코드를 고유의 key값으로 데이터(value)를 저장함.

그래서 많은 큰 범위 내 많은 양의 데이터도 제한된 메모리 내에서 효율적으로 저장 및 관리할 수 있으며, 데이터마다 고유의 key값을 index로 활용하기 때문에 데이터 입력과 탐색 시 O(1)의 시간복잡도를 가짐.

 

3. 정렬, 해시 사용 X
   • 2번 로직 그대로 HashMap을 사용하지 않음
   • phone_book 배열 길이만큼 중첩for문으로 i번째 번호가 나머지 번호와 접두사 관계에 있는지 확인
   • 정확성 시간 0.02~0.05ms / 효율성 시간 0.04~0.05ms

 

솔루션

1. 일반 정렬 후 탐색

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book); // 문자열 오름차순 정렬

        // i번째가 i+1번째의 접두사인지 확인
        for(int i = 0, size = phone_book.length; i < size - 1; i++){
            if(phone_book[i+1].startsWith(phone_book[i])){
                answer = false;
                break;
            }
        }
         return answer;
    }
}

 

 

2. 해시

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;

        HashMap<Integer,String> map = new HashMap<Integer,String>();

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

        //서로 접두사 관계인지 확인
        for(int i=0;i<map.size();i++){
            String a = map.get(i);
            for(int j=i+1; j<map.size(); j++) {
                if(a.startsWith(phone_book[j]) || phone_book[j].startsWith(a)) {
                    answer = false;
                    break;
                }
            }

            if(answer == false)
                break;
        }
        return answer;
    }
}

 

 

3. 정렬, 해시 사용 X => 제일빠름

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;

    // hashmap 사용 X
    // HashMap<Integer,String> map = new HashMap<Integer,String>();
        int n = phone_book.length;

        for(int i=0;i<n;i++){
            String a = phone_book[i];
            for(int j=i+1; j<n; j++) {
                if(a.startsWith(phone_book[j]) || phone_book[j].startsWith(a)) {
                    answer = false;
                    break;
                }
            }

            if(!answer)
                break;
        }
        return answer;
    }
}

 

리뷰

• 여러 방법으로 문제를 풀어봤지만, 굳이 해시를 사용해야하는 이유를 아직 잘 모르겠다