프로그래머스 코딩테스트 연습 > 해시 > 전화번호 목록 (Java)

 

문제해설

 

한 번호가 다른 번호의 접두어인 경우가 있는지 확인하는 문제입니다. 단, 주어진 번호가 1개 이상 1,000,000개 이하로 주어지므로 효율적인 자료구조와 알고리즘을 사용해야합니다.

 

 

문제풀이

 

각 전화번호 모두 접두어가 될 가능성이 있으므로 전화번호를 key, true 값을 value로 하는 해시맵을 준비합니다. 각 전화번호를 참조하면서 전화번호의 부분수열이 해시맵의 key로 등록되어 있는지 확인합니다. 이미 등록이 되어있다면 접두어가 있다는뜻이므로 false를 반환하고 없다면 참조하는 전화번호를 해시맵에 등록합니다. 모든 전화번호를 탐색해도 접두어가 발견되지 않는다면 true를 반환합니다.

주의할점은, 길이가 짧은 전화번호부터 먼저 해시맵에 등록을 해야 접두어가 있는 모든 경우를 찾을 수 있습니다.

 

 

1. HashMap 선언

2. phone_book 배열 오름차순 정렬

3. 각 전화번호 부분수열 HashMap에 있는지 확인

4. 있으면 접두어가 있는 경우 -> false 반환

5. 없으면 전화번호 HashMap에 등록

6. 모든 전화번호 탐색해도 접두어 없었다면 true 반환

 

 

코드

 

import java.util.HashMap;
import java.util.Arrays;
 
class Solution {
    public boolean solution(String[] phone_book) {
        HashMap<String, Boolean> map = new HashMap<>();
        Arrays.sort(phone_book);
        for (String number : phone_book) {
            String temp = "";
            for (int i = 0 ; i < number.length() ; i++) {
                temp += number.charAt(i);
                if (map.containsKey(temp)) {
                    return false;
                }
            }
            map.put(number, true);
        }
        return true;
    }
}

 

 

결과