[해시] 전화번호 목록

문제

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

프로그래머스

 

풀이

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public boolean solution(String[] phone_book) {
        List<String> sortedPhones = Arrays.stream(phone_book)
            .sorted()
            .collect(Collectors.toList());
        for(int i = 0 ; i < sortedPhones.size()-1 ; i++){
            if(sortedPhones.get(i+1).startsWith((sortedPhones.get(i)))){
                return false;   
            }
        }
           
        return true;
    }
}

 

해설

나는 '비교'하는 문제에 약한 편이기 때문에, 아래 힌트를 보고 문제를 풀 수 있었다.

정렬되어 있음이 보장된다면, phone_book[i] 를 접두사로 갖는 가장 가까운 phone_book[n]의 n이 어디일까요?

문자열 배열을 정렬하고 나면, 

나의 바로 다음 문자열이 내 접두사를 동일하게 가지고 있지 않다면 다른 모든 값들은 내 접두사를 동일하게 가질 수가 없다.

접두사가 동일하면 정렬을 했을 때 바로 다음 값으로 올 수 밖에 없기 때문.

 

예를들어, 아래 값들을 정렬하면

[123, 1243, 12345] -> [123, 12345, 1243]

접두사가 같은 경우가 바로 다음 값으로 오는 것을 알 수 있다.

 

그러므로 바로 다음값만 string의 startsWith()을 활용하여 접두사 여부를 체크한다.

 

참고로 나는 List컬렉션을 만들었으나, 그냥 Arrays.sort(phone_book)을 해도 정렬이 된다.

이럴 경우 쓸모없는 자원을 사용하지 않으므로 더 효율적이다.

후기

비교하는 문제의 경우 전체를 모두 비교해서 풀리는 경우도 물론 있겠지만,

좀 더 효율적인 방법이 있을 확률이 매우 높다는 것을 기억해두자 !

그리고 예시를 통해 문제를 이해하는 습관을 들여놓는 것도 필요하다.