프로그래머스 전화번호 목록 풀이 HashMap, HashSet 두 가지 해법

오늘의 두 번째 문제는, 프로그래머스 전화번호 목록 이다. 이 역시 Hash 관련된 문제이다. 이렇게 어떤 자료구조를 사용할 지 알려줘서 문제해결의 방향성을 잡기가 쉽다.

실제 테스트시에는 어떤 자료구조를 사용할 지 정하는 게 가장 어렵다고 생각한드아..

 

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

 

프로그래머스 전화번호 목록 문제를 간단히 요약하면 아래와 같다.

• 전화번호 목록 중에서 어떤 전화번호가 다른 전화번호의 접두사가 되는지 체크하는 문제
• 접두사가 되는 것이 하나라도 있으면 false

 

어떻게 풀까?

일단은 전체를 돌면서 접두사가 되는 것이 있는지 체크해야하는데, 가장 먼저 떠오른 것은 HashMap에 모든 건을 넣어서 Hashing 하고 전체 리스트를 돌면서 해당건의 접두사가 되는 전화번호가 있는지 검사하는 방식이다.

접두사를 검사하는 방식은 String에 subString으로 모든 문자열 조합을 containsKey를 활용해서 체크하는 방식이다.

이러면 전체 건 탐색 O(n)에 containsKey O(1) 만 하변 되니까 O(n) 복잡도로 해결할 수 있다.

 

풀이 코드

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        HashMap<String, Integer> map = new HashMap<>();
        
        // 전체 전화번호부 목록을 해싱
        for(int i=0; i<phone_book.length; i++){
            map.put(phone_book[i], 0);
        }
        
        // 전체 전화번호에 대해서 접두어가 있는지 체크
        for(int i=0; i<phone_book.length; i++){
            String tempStr = "";
            for(int j=1; j<phone_book[i].length(); j++){
                if(map.containsKey(phone_book[i].substring(0, j))){
                    answer = false;
                    break;
                }
            }
            
            if(!answer){
                break;
            }
        }
        
        return answer;
    }
}

그렇게 풀어 본 프로그래머스 전화번호 목록 문제는 위와 같다. 일부 비효율적인 코드가 있을 수도 있으나, 큰 흐름에서는 문제가 없어 보인다.

문제를 풀고 나니 HashMap의 key, value 중 value가 의미가 없어졌다. 앞에 푼 문제처럼 HashSet으로 더 간단하고 깔끔하게 처리가 가능해보였다.

 

HashSet을 사용해서 다시 풀어봄

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        HashSet<String> hs = new HashSet<>();
        
        // 전체 전화번호부 목록을 해싱
        for(int i=0; i<phone_book.length; i++){
            hs.add(phone_book[i]);
        }
        
        // 전체 전화번호에 대해서 접두어가 있는지 체크
        for(int i=0; i<phone_book.length; i++){
            String tempStr = "";
            for(int j=1; j<phone_book[i].length(); j++){
                if(hs.contains(phone_book[i].substring(0, j))){
                    answer = false;
                    break;
                }
            }
            
            if(!answer){
                break;
            }
        }
        
        return answer;
    }
}

기존 소스를 살짝만 변형해서 HashSet으로 풀어 보았다. 이게 더 명확한 것 같다.

 

마침 문제를 푼 후 다른사람의 기깔나는 풀이가 궁금해서 찾아보았다.

다른 사람의 풀이

다른 사람의 풀이를 누르면 인기많은(?) 풀이가 보인다.

 

기가 멕힌다.

기가 멕히는 다른 사람의 풀이.. 고수다. 내 소스는 무려 30줄에 달하는데, 10줄만에 풀이해버렸다. 

하지만 Hash를 사용하지 않고 그냥 배열의 이중포문이라 복잡도는 올라가는 소스였다. 

 

아무튼, 풀이는 간단했고 여기서 사용한 HashMap에 대해서도 살짝 정리해보자.

HashMap, 정말 많이 쓰는 자료구조

오늘도 열일 gpt

HashMap의 주요 특징은 아래와 같다.

• Key/Value 셋을 저장함.
• 검색, 삽입, 삭제에서 빠른성능. 기본적으로 O(1)
• 대량의 데이터에 적합, 정렬은 x
• 해시출동 : 서로 다른 키가 동일한 해시 값을 가질 때 발생

관련 함수는 아래와 같다.

• put(key, value)
• get, remove, containsKey, containsValue
• ketSet, values, size

 

이렇게 프로그래머스 전화번호 목록 문제를 HashSet, HashMap으로 풀어보고 HashMap에 대해서도 간단히 공부해 보았다.

끝.