[프로그래머스] (lv.2) 전화번호 목록(java)

웜시의 뜨뜻한 개발로그·2023년 10월 23일

코딩테스트

목록 보기

32/37

<문제>

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

접두어! 어떻게 풀까 고민하다가 가장 짧은 번호를 찾아서
그 길이대로 잘라 HashSet 써서 hashSet이랑 배열의 길이를 비교해주면 풀리겠다 생각했었음!

<나의 풀이 - 실패한 코드>

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        String[] pre_book = phone_book;
        Arrays.sort(pre_book, Comparator.comparing(String::length));
        int len = pre_book[0].length();
        Set set = new HashSet();
        set.add(pre_book[0]);
        for (int i=1; i<pre_book.length; i++) {
            set.add(pre_book[i].substring(0, len));
        }
        if (set.size() != pre_book.length) {
            return false;
        }
        return true;
    }
}

처음엔 이렇게 풀었는데 효율성 테스트도 모두 포함해도 이상하게 11, 14 번 케이스는 통과하지 못했다ㅠ

그래서 계속 왜 못풀었을까 생각하다가 힌트를 얻어 반례를 생각해보니

phone_book ["123", "1197", "557713", "11987543"] / true < 이 케이스가 존재했다.
나의 코드대로라면 이 케이스의 결과는 false 가 나와야 하지만 1197은 11987543의 접두어가 아니다. 즉, 단순히 가장 짧은 길이로 자르면 이러한 예외가 발생하는 것이다.

그래서 추가적으로 가장 짧은 문자열로 잘라준 후,
접두어가 되는지도 판별해주는 코드를 추가해주었다.

<나의 풀이 - 성공한 코드>

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {        
    HashMap<String, String> map = new HashMap<>();
        // 길이가 가장 짧은 순으로 정렬
        Arrays.sort(phone_book, Comparator.comparing(String::length));
        // 가장 짧은 번호의 길이
        int len = phone_book[0].length();
        // 배열을 돌며 가장 짧은 길이대로 잘라줌.
        for (String num : phone_book) {
            String key = num.substring(0, len);
            if (map.containsKey(key)) {	
            // 만약 key 값이 중복된다면 (ex. 1197, 119845)
            // key값에 해당하는 value를 불러옴.
                String value = map.get(key);    
                if (num.startsWith(value)) {    
                // key가 이미 존재하면, value 가 접두사가 되는지 한번 더 확인해줌.
               // 접두사가 되려면 어떤 전번의 전체 길이가 다른 수의 접두사인지 확인해주면 됨.
                    return false;
                }
            }
            map.put(key, num);
        }
        return true;
    }
}