Java - [프로그래머스 Lv.2]42577 - 전화번호 목록

출처

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

프로그래머스

 

문제

 

알고리즘 고득점 Kit에 해쉬 부분에 있는 문제입니다. 

 

문제는 간단합니다. 여러 전화번호가 적힌 전화번호 배열이 주어지면, 어떤 한 번호가 다른 번호의 접두어인 경우가 있으면 false, 없으면 true를 반환하는 문제입니다.

 

솔직히 이 문제를 보고 든 생각은, '이게 왜 굳이굳이 해쉬 카테고리에 있는지..?'에 대한 의문이였습니다.

 

먼저, 가장 단순 무식하게 풀 수 있는 방법으로는, 각각의 원소 x에 대하여 모든 배열을 돌면서 확인하는 방법이 있습니다.

for (int i = 0; i < phone_book.length; i++) {
    for (int j = i + 1; j < phone_book.length; j++) {
        if (phone_book[j].startsWith(phone_book[i])) {
            return false;
        }
    }
}

이렇게 원소 i를 기준으로 뒤의 원소가 i로 시작하는지만 보면 되는 단순한 문제라고 생각했습니다.

 

실제로 풀어서 제출해보진 않았지만, 효율성의 문제가 있을 수 도 있겠다는 생각이 들었습니다.

 

다음으로는 문자열을 정렬 한 뒤, 기준 원소 바로 뒤의 원소가 기준 원소로 시작하는지 검사하여 푸는 방법입니다.

Arrays.sort(phone_book);

for (int i = 0; i < phone_book.length - 1; i++) {
    String s = phone_book[i];
    if (phone_book[i + 1].startsWith(s)) {
        return false;
    }
}
return true;

 

이 방법은 효율성 검사에도 걸리지 않고, 단순합니다. 솔직히 이 방법이 정석적으로 푸는게 아닌가? 라는 생각도 들었습니다.

 

실제 코딩테스트에서는, 문제의 분류를 알려주지도 않을 뿐더러 명확히 구분하지 않는 경우도 많습니다. 그렇기 때문에 실제 코딩테스트에서 이 문제를 마주쳤다면 가장 먼저 떠오른 위 두가지 방법으로 푸는게 맞습니다. 하지만 저는, 해쉬에 대해 공부하고자 해당 문제를 풀기 때문에 , 프로그래머스에서 정해준 해쉬를 사용하여 문제를 해결해보겠습니다.

 

해쉬를 이용한 풀이

이 풀이 또한 어렵지는 않습니다. HashMap에 모든 전화번호를 넣고, 기준 번호의 접두어가 HashMap 내부에 Key로 존재하는지, 아닌지  판단하면 됩니다.

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        Map<String, Integer> map = new HashMap<>();

        for (String x : phone_book) {
            map.put(x, 1);
        }
        for (int i = 0; i < phone_book.length; i++) {
            for (int j = 1; j < phone_book[i].length(); j++) {
                if (map.containsKey(phone_book[i].substring(0, j))) {
                    return false;
                }
            }
        }
        return true;
    }
}

 

key와 value의 쌍으로 HashMap에 넣습니다. (솔직히 value도 쓸모가 없으니까 1로 넣어줬는데, 이럴거면 그냥 set를 쓰는게..)

 

아무튼, 이제 배열을 순회하며 subString으로 접두어를 하나씩 추출해보며 잘라낸 접두어가 현재 map에 존재한다면, false를 리턴하고 발견하지 못했으면 true를 반환합니다.

 

위에 제가 소개한 방법 외에도, 많은 다양한 방법을 적용해서 풀 수 있는 문제입니다. 상황에 잘 맞게 적용해서 푸시면 좋을 것 같습니다.