전화번호 목록

 

https://school.programmers.co.kr/learn/courses/30/lessons/42577#

프로그래머스

 

Level 2

 

대표적인 Hash 를 사용해서 푸는 문제, 전화번호의 접두가 다른 전화번호를 포함하는지 찾아야한다. 

 

필자는 전화번호 목록을 반복문으로 탐색하기 이전에 전화번호 목록을 정렬했다. 

자바 내장 문자열 배열 정렬 기준은 사전식 기준이기에 나는 사전식 이전에 문자열이 더 짧을 경우를 추가헀다. 

즉, 새로운 기준으로 배열을 짧은 전화번호 우선 정렬 후 같은 길이의 문자열에 한해서는 사전식으로 정렬할 수 있다. 

 

이후 정렬된 배열을 순차 탐색하여 다음 전화번호는 항상 현재 전화번호의 길이만큼만 접두 번호를 탐색하고 만약 길이 내에 HashMap 안에 Key 문자열이 존재한다면 즉시 false 를 반환, 모든 전화번호를 확인했음에도 접두 번호가 없으면 true 를 반환하도록 했다. 

 

import java.util.*;

public class Solution {
    public boolean solution(String[] phone_book) { //전화번호 목록
        Comparator<String> comparator = new Comparator<String>() { //커스텀 정렬 인터페이스
            @Override
            public int compare(String o1, String o2) { //단순 사전식 정렬이 아닌 문자열 길이가 짧은 것 우선 -> 사전식 으로 변경
                if(o1.length() == o2.length()){
                    return o1.compareTo(o2);
                }
                return o1.length() - o2.length();
            }
        };
        Arrays.sort(phone_book, comparator); //정렬 짧은 것 우선 else 사전식 으로 정렬
        HashMap<String, Integer> bookMap = new HashMap<String, Integer>(); //해시 테이블
        int maxNumberLen = phone_book[0].length(); //가장 짧은 전화번호 길이부터 시작
        for(String phoneNumber : phone_book){
            StringBuilder key = new StringBuilder();
            for(int idx = 0; idx < maxNumberLen; idx++){ //전화번호를 정렬 상 자신 이전의 전화번호의 길이 만큼만 확인
                key.append(phoneNumber.charAt(idx)); //번호 1byte 씩 넘어가며 해시 키값 업데이트
                if(bookMap.containsKey(key.toString())) return false; //만약 해시 테이블에 키가 존재하면 바로 false 반환
            }
            bookMap.put(phoneNumber, phoneNumber.length()); //접두어 포함되는 전화번호가 없으므로 테이블 추가
            maxNumberLen = bookMap.get(phoneNumber); //다음으로 올 전화번호를 자신의 길이만큼 접두어 확인
        }
        return true; //모든 전화번호가 접두어 중복이 없으므로 true 반환
    }
}