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

문제 설명

 

 

코딩테스트 연습 - 전화번호 목록

 

 

 

풀이

소스 코드 : Fail(시간초과)

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        boolean flag = false;

        for (int i = 0; i < phone_book.length - 1; i++) {
            for (int j = i + 1; j < phone_book.length; j++) {
                if (phone_book[j].length() >= phone_book[i].length() && phone_book[j].startsWith(phone_book[i])
                    || phone_book[i].length() >= phone_book[j].length() && phone_book[i].startsWith(phone_book[j])) {
                    answer = false;
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }

        return answer;
    }
}

 

문제원인 분석

처음 문제 접근 방식은 직관적으로 주어진 전화번호 배열의 요소(Element) 하나를 다른 요소들의 접두어에 해당되는지 하나하나 체크하도록 했습니다. 이를 위해서(완전 탐색을 위해서) 2중 for문을 사용했고 접두어가 하나라도 발견되면 2중 for문을 break하도록 했습니다.

 

하지만 결론적으로 효율성 테스트에서 시간 초과가 발생했는데, 이는 주어진 전화번호 배열 요소가 최대 1백만개인데, 2중 for문의 시간복잡도 특성상 최악의 경우 O(N^2)에 해당하기 때문에 발생한 것입니다. 따라서 완전 탐색이 아닌 "해시"를 통해 탐색(접두어 해당 여부 확인) 속도를 증가시키고자 했습니다.

 

소스 코드 : Success

import java.util.SortedMap;
import java.util.TreeMap;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;

        TreeMap<String, Object> map = new TreeMap<>();

        for (String phone : phone_book) {
            map.put(phone, null);
        }

        for (String key : map.keySet()) {
            SortedMap<String, Object> tailMap = map.tailMap(key, false);
            if (!tailMap.isEmpty() && tailMap.firstKey().startsWith(key)) {
                answer = false;
                break;
            }
        }

        return answer;
    }
}

 

풀이 회고

우선 주어진 전화번호 문자열 배열의 요소 값들을 TreeMap에 Key 값으로 저장시키도록 했습니다. 이때 TreeMap의 경우 레드-블랙 트리 기반으로 데이터를 저장하며 정렬(문자열의 경우 유니코드 순)을 해주는데 이로 인해 HashMap 보다는 다소 성능이 안 좋습니다. 그래도 정렬이 된 상태의 데이터(Key)를 조회할 수 있기 때문에 이를 활용했습니다.

 

모든 요소 값들의 저장을 마친 후에 해당 TreeMap에 저장된 Key 값별로 해당 TreeMap에 접두어가 존재하는지 확인하도록 했습니다. 이때 사용한 것은 TreeMap의 tailMap 메서드인데 첫 번째 인자로 특정 값을 두면, 그 값과 같거나 접두어가 같은(+길이가 더긴) Key 값들이 차례대로 정렬(동일한 Key 값 -> 접두어가 같은 Key 값 -> 해당되지 않는 Key 값)된 SortedMap 타입의 자료구조가 반환됩니다. 또한 두 번째 인자로 false를 두면, 첫 번째 인자로 둔 특정 값과 동일한 Key 값은 제외됩니다. 이는 자기 자신의 Key 값으로 자기 자신을 찾는 것을 방지하기 위함입니다.

 

그리하여 tailMap에 첫 번째 인자로는 접두어 역할을 하는(탐색하고자 하는) Key 값을 두었고, 두 번째 인자로는 false를 두어 SortedMap을 얻어냈습니다. 여기서 만일 반환된 SortedMap 자료구조가 null이 아니고 SortedMap의 첫 번째 Key 값 요소(firstKey())와 앞서 tailMap 메서드 첫 번째 인자에 둔 Key 값이 같다면 해당 전화번호 목록(배열)에 어떤 번호가 다른 번호의 접두어라는 것을 확인할 수 있게 됩니다.

 

 

참고자료

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