해시- 전화번호 목록

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

1. phone_book의 길이는 1 이상 1,000,000 이하입니다.
2. 각 전화번호의 길이는 1 이상 20 이하입니다.

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

package jungja_study;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class PhoneNumberList {

    public boolean solutionh(String[] phone_book) {

        boolean answer = true;
        Map<Integer, String> map = new HashMap<>();

        Arrays.sort(phone_book);

        for (int i = 0; i < phone_book.length; i++) {
            map.put(i, phone_book[i]);
        }

        for (int i = 0; i < phone_book.length; i++) {
            System.out.println(map.get(i));
        }


        for (int i = 0; i < map.size() - 1; i++) {
            if (map.get(i).length() < map.get(i + 1).length()) {
                if (map.get(i + 1).startsWith(map.get(i))) {
                    answer = false;
                    break;
                }
            }
        }

        return answer;
    }


    public static void main(String[] args) {

        PhoneNumberList phoneNumberList = new PhoneNumberList();
        String[] phone_book = {"119", "97674223", "1195524421"};
        String[] phone_book2 = {"123", "456", "789"};
        String[] phone_book3 = {"12", "123", "1235", "567", "88"};
        System.out.println(phoneNumberList.solutionh(phone_book));
        System.out.println(phoneNumberList.solutionh(phone_book2));
        System.out.println(phoneNumberList.solutionh(phone_book3));

    }
}

사실 해시 관련 문제이기 대문에 해시로 엮어서 풀려고 많은 생각을 했지만... 테스트 케이스 7,8에서 계속 에러가 발생하여서.. 다른 풀이의 답을 참조하게 되었습니다. 하지만 대부분 풀이를 보면 해시를 사용하기 보다는 정렬을 이용해서 문자열 메소드 startWith를 이용하여 푸는게 가장 깔끔하게 풀어집니다. 이 문제의 핵심은 전화번호가 들어가 있는 phone_number 배열에서 각각의 전화번호가 다른 인덱스에 있는 전화번호의 접두사인지 확인하여 false, true 둘 중에 하나를 리턴하면 되는 문제입니다.

저 같은 경우에는 HashMap 객체를 이용하여 전화번호 목록에 있는 번호들을 넣었지만, 사실 여기서 가장 핵심은 Arrays.sort() 정렬 메소드 입니다. 굳이 해시를 이용하지 않아도 간단하게.. 풀리는 문제였습니다.
sort() 메소드로 전화번호 목록이 담긴 배열을 넣으면 사전식으로 정렬이 되기 때문에 어떤 전화번호의 접두사가 되는 전화번호가 앞 순서에 위치하게 되기 때문에 정렬된 전화번호 리스트를 순회하여 다음에 오는 전화번호가 현재 전화번호로 시작하는지 체크를 해주면 됩니다.

프로그래머스에서 Best Practice를 보면 정렬없이 아래와 같이 풀수도 있습니다.

for(int i=0; i<phone_book.length-1; i++) {
    for(int j=i+1; j<phone_book.length; j++) {
        if(phone_book[i].startsWith(phone_book[j])) {return false;}
        if(phone_book[j].startsWith(phone_book[i])) {return false;}

    }
}

위와 같은 방식으로 풀면 문자열 길이를 체크하지 않고 순회하며 비교가 가능합니다.