[프로그래머스/Java] 전화번호 목록(hash 문제) 풀이

프로그래머스 알고리즘 고득점 Kit의 해시 문제인 전화번호 목록을 자바로 풀어보았다. 

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

프로그래머스

 

 

이 문제는 sort를 이용하는 것이 핵심이다. sort를 이용하지 않으면, 이중 루프를 이용하여 모든 요소를 서로 비교해야 하지만, sort를 이용하면 이웃한 element끼리만 비교하면 되기 때문이다.

따라서 우선 Arrays.sort() 함수를 통해 주어진 String array를 정렬한 후, 이웃한 element들끼리만 비교해 준다. 정렬이 되어있는 상태이므로, 뒷 element는 앞 element의 접두어가 될 수 없다. 이웃한 element들 중 오직 더 앞선 element만이 뒤따른 element의 접두어가 될 수 있다. 또한, 만약 하나의 element가 여러 가지 다른 element의 접두어가 된다면 i+2, i+3번째 역시 i번째 element가 접두어가 되는 전화번호일 수 있으나. 이렇게 되면 i+1번째도 무조건적으로 i번째 element가 접두어가 되므로, 굳이 고려할 필요가 없다. 우리는 전화번호 목록 내에 접두어가 성립하는 경우가 있는지 없는지 여부만 확인하면 되기 때문이다. 

따라서 아래 코드에서는 i-1번째가 i번째 element의 접두어인지를 확인한다. 

import java.util.Arrays; //sort 함수
 
class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book); //String array 정렬
        int len = phone_book.length; //전체 string array 길이
        for (int i = 1; i < len; i++) {
            int pre_len = phone_book[i-1].length();
            if (pre_len > phone_book[i].length()) continue;
            if (phone_book[i-1].equals(phone_book[i].substring(0, pre_len)))
                return false;
        }        
        return true;
    }
}