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

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

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

아이디어

이 문제에서는 각 번호 사이의 포함관계가 아니라, 접두어 관계가 있는지 여부를 판단하는 것이 목적이기 때문에 주어진 전화번호 String들 중 가장 짧은 길이를 찾고, 각 전화번호의 앞에서부터 해당 길이만큼만 비교하는 방법을 취했다.

즉, 가장 짧은 길이가 n 이라면 전화번호들의 앞 n자리 글자들만 떼어내어 이를 key로 사용하는 map에 put 해 주었다.

 

하지만, 여기서 value를 해당 key를 가지는 전화번호의 갯수(int)로 할 경우 테스트 8, 테스트 11에서 실패하게 된다.

이는 주어진 테스트 케이스가 "12", "235", "2345" 일 경우, 가장 짧은 길이가 2 이므로 앞의 두 자리만 비교하게 되어 "235" 와 "2345"의 key 값이 서로 동일해지기 때문이다.

이를 보완하기 위해서 value를 해당 key의 integer counter로 삼지 않고 List<String>의 형태를 사용하여 해당 key값을 가지는 원본 전화번호를 저장하도록 하였고, 해당 List의 길이가 2 이상일 경우에만 해당 리스트 내에서 접두어 관계를 직접 비교하도록 해 주었다.

 

List 내에 속한 String들을 직접 비교 할 때에는 원소들을 길이의 오름차순으로 정렬한 후 앞에 있는 원소가 뒷쪽에 모든 원소들의 접두어인지 확인하는 방식을 사용했다.

 

소스코드

package hash;

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        // 1. 가장 짧은 길이 찾기
        int shortest = Integer.MAX_VALUE;
        for (String number : phone_book) {
            shortest = Math.min(shortest, number.length());
        }

        // 2. 해당 길이만큼의 substring을 key로 하는 map 만들기
        Map<String, List<String>> map = new HashMap<>();
        // key: 전화번호 앞 n자리 // value: 해당 String의 List
        for (String number : phone_book) {
            String prefix = number.substring(0, shortest);
            List<String> list = map.getOrDefault(prefix, new ArrayList<>());
            list.add(number);
            map.put(prefix, list);
        }

        // 3. prefix 찾기 : list의 원소 갯수가 2개 이상인 경우에만
        Set<String> keySet = map.keySet();
        for (String currentKey : keySet) {
            List<String> list = map.get(currentKey);
            if (list.size() > 1) {
                if (hasPrefixInside(list)) {
                    return false;
                }
            }
        }

        return true;
    }

    private boolean hasPrefixInside(List<String> list) {
    // 길이의 오름차순으로 정렬
        list.sort(Comparator.comparingInt(String::length));
        int size = list.size();
        for (int i = 0; i < size - 1; i++) {
            for (int j = i + 1; j < size; j++) {
                if (list.get(j).startsWith(list.get(i))) {
                    return true;
                }
            }
        }
        return false;
    }
}