[프로그래머스,Level 2] 전화번호 목록(JAVA 구현)

- 첫 풀이 및 정답풀이

  우선 이 문제는 해시로 분류되어 있는 문제이지만, 반복문을 이용해도 풀 수 있을 것 같아 시도해보아 풀 수 있었다. 문제 자체는 매우 간단하다. 한 전화번호가 다른 한 전화번호의 접두사가 된다면 false를 리턴하면 된다. 이 말은 접두사가 될 수 있는 전화번호가 하나라도 존재한다면 바로 false를 리턴하면 된다는 소리이기 때문에 다른 모든 전화번호를 탐색할 필요가 없어진다.

 

  본인은 문자열 배열에서 하나의 기준점을 두고, 다른 전화번호와 비교하는 2중 반복문을 사용하였으며 이때, 비교하는 전화번호는 반드시 비교되는 문자열에 비해 길이가 짧아야 한다. 이는 애초에 길이가 긴 문자열이 자신보다 길이가 짧은 문자열의 접두사가 될 수 없기 때문이다.

 

* for문을 이용한 풀이

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        // 1. 기준점 반복문.
        for(int i = 0;i<phone_book.length;i++){
            // 2. 비교대상 반복문.
            for(int j = 0 ; j<phone_book.length;j++){
                // 3. 자신은 스킵.
                if(i == j) continue;
                // 4. s_idx에 길이가 짧은 문자열 인덱스를 저장, b_idx에 길이가 긴 문자열 인덱스를 저장.
                int s_idx = phone_book[i].length() <phone_book[j].length() ? i : j;
                int b_idx = phone_book[i].length() <phone_book[j].length() ? j : i;
                // 5. 길이가 긴 문자열에서 길이가 짧은 문자열의 길이만큼 substring.
                String str = phone_book[b_idx].substring(0,phone_book[s_idx].length());
                // 6. compareTo의 결과가 0이라면 같은 문자열이므로 false 리턴.
                if(phone_book[s_idx].compareTo(str) == 0) return false;                
            }
        }
        return answer;
    }
}

  

 

---

문제의 카테고리에 맞게 해시를 이용한 방법을 위해 해시 맵을 사용해 추가적으로 풀어보았다. 기본적인 개념은 동일하며, 코드 롤 좀 더 줄여보았다.

* 해시맵을 이용한 풀이

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        // 1. 해시맵<전화번호, 전화번호 길이> 저장.
        HashMap<String,Integer> map = new HashMap<>();
        
        // 2. 해시맵 데이터 입력.
        for(String str:phone_book){
            map.put(str,str.length());
        }
        
        // 3. 기준점이 되는 전화번호를 탐색하는 반복문.
        for(String str:phone_book){
            // 4. 기준점의 전화번호 길이 저장.
            int len = str.length();
            // 5. 해시맵 탐색.
            for(Entry<String,Integer> entry : map.entrySet()){
                String key = entry.getKey();
                int value = entry.getValue();
                // 6. 기준점과 비교되는 문자열이 같은 문자열이면 continue.
                if(str.compareTo(key)==0) continue;
                // 7. 기준점의 전화번호 길이와 비교되는 해시맵에 저장된 key 전화번호의 value 길이 중 작은 값을 취한다.
                int idx = len < value ? len : value;
                // 8. 두 문자열 모두 0~idx까지 잘라 비교
                if(str.substring(0,idx).compareTo(key.substring(0,idx)) == 0)
                    return false;
            }
        }
        
        return answer;
    }
}

  이번 문제는 결과적으로 효율성면에서 for문이 좋은 것 같다.