[프로그래머스] Hash(해시) - 전화번호 목록 (Java)

프로그래머스 코딩테스트 연습 - 해시(Hash) : 네트워크 (https://programmers.co.kr/learn/courses/30/lessons/42577) 

코딩테스트 연습 - 전화번호 목록 | 프로그래머스

우선 Hash 카테고리에 맞게 해시를 이용한 문제풀이를 해보았습니다. 저는 일단 HashMap을 이용했는데 Map의 특징은 우선 key의 중복을 허용하지 않는다는 것입니다. 이러한 특징을 이용해 phone_book에 저장된 전화번호 String의 길이를 key값으로 잡았습니다. 전화번호 길이를 key값으로 잡은 이유는 길이가 더 짧은 전화번호를 가지고 길이가 더 긴 전화번호의 접두사인지 아닌지를 check하기 위함입니다. 

 

HashMap에 길이가 같은 여러 전화번호를 add해야 하는 상황에는 해당 길이의 key에 대응하는 value를 Set으로 정의해서 일종의 분리연결법을 적용했습니다. (사실 더 정확한 분리연결법을 적용하려면 LinkedList와 같은 구조를 이용해야 합니다. 저는 순서상관없이 단순 조회만을 원하기 때문에 Set을 사용했습니다.)

 

이렇게 모든 전화번호에 대한 HashMap을 완성했다면 길이가 가장 짧은 전화번호부터 시작해서 길이가 더 긴 전화번호의 접두사인지 아닌지를 조회하는 구문을 만들었습니다.

import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;
import java.util.Iterator;
 
class Solution {
    public boolean solution(String[] phone_book) {
        
        HashMap<Integer, Set<String>> phoneMap = new HashMap<>();
        Set<String> phoneSet = null;
        for(String phone : phone_book){
            int length = phone.length();
            if(phoneMap.get(length) == null){
                phoneSet = new HashSet<>();
                phoneSet.add(phone); 
            } else{
                phoneSet = phoneMap.get(length);
                phoneSet.add(phone);
            }
            
            phoneMap.put(length, phoneSet);
        }
        
        for(int key : phoneMap.keySet()){
            Iterator<String> iter = phoneMap.get(key).iterator(); 
            while (iter.hasNext()){
                String phoneNum = iter.next();
                
                for(int searchKey : phoneMap.keySet()){
                    if(key == searchKey) continue;
                    
                    Iterator<String> searchIter = phoneMap.get(searchKey).iterator(); 
                    while (searchIter.hasNext()){
                        String longerPhoneNum = searchIter.next();
                        if(longerPhoneNum.indexOf(phoneNum) == 0){
                            return false;
                        }
                    }
                }
            }
        }
        
        return true;
    }
}

 

출처

- HashMap에 대한 설명 : https://vaert.tistory.com/107

- Hash에 대한 기본구조 설명 : https://hyeonstorage.tistory.com/265