해시(Hash)를 활용한 알고리즘 문제풀이

오늘 푼 문제: 전화번호 목록

• 입력: 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 매개변수로 주어집니다.
• 출력: 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 출력합니다.

예제 코드1 (Without Using Hash)

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book); // 문자열 배열을 오름차순으로 정렬합니다.
        for (int i = 0; i < phone_book.length - 1; i++) {
            if (phone_book[i + 1].startsWith(phone_book[i])) return false;
            // 해당 인덱스의 전화번호가 다음 인덱스의 접두어인 경우 false를 return합니다.
        }
        return answer;
    }
}

• 처음에는 이중 for문으로 탐색했었습니다. => 당연히 시간 초과!
• 그래서 해시 알고리즘 쓰는 문제인줄 모르고 특정 전화번호가 비교하는 전화번호보다 길이가 작거나 같고, 해당 번호로 전화번호가 시작되어야 하기 때문에, 정렬을 하여 각 인덱스와 다음인덱스를 비교하면 된다고 생각하였습니다.
• 그래서 Arrays.sort()로 오름차순으로 문자열 배열을 정렬하였고, String.startsWith() 매서드로 비교를 하였습니다.

예제 코드 2 (With Using Hash)

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        // 해싱을 위한 Map 선언
        Map<String, Integer> map = new HashMap();
        
        for (String phone_number : phone_book) map.put(phone_number, 5);
        // String[] phone_book 배열 length만큼 loop를 돌며 map에 전화번호 입력
        
        for (int x = 0; x < phone_book.length; x++) {
            for (int y = 0; y < phone_book[x].length(); y++) {
                if (map.containsKey(phone_book[x].substring(0, y))) return false;
            }
        }
        return answer;
    }
}

• 중복 데이터를 제거하고, 전화번호들에 대하여 빠르게 조회하기 위해 HashMap을 사용했습니다.
• 처음에 모든 전화번호들을 HashMap에 저장합니다. 이 때 key-value 값으로 저장되는데 key만 사용하기 때문에 value는 임의의 정수값으로 저장하였습니다.
• 모든 전화번호들에 대하여 loop를 돌며 해당 전화번호를 1자리부터 n자리까지 substring하여 해당 값이 map에 존재하는지 확인하여 답을 구합니다.

회고

• 문제 풀이 시 필요 기능을 정의하는 습관을 들여보겠습니다. 너무 요구사항을 정리하지 않고 푸는 습관이 있는 것 같습니다.
• 마크다운 문법을 공부할 필요가 있어보입니다.
• 개더타운에서 춤을 출려면 X를 누르면 됩니다. 쌈@뽕하게 춤을 추는 것을 볼 수 있습니다.