[프로그래머스 고득점 kit] 해시 Level2 전화번호 목록

문제 설명

 

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

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

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

제한 사항

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

입출력 예제

 

phone_book                                                                                              return

[119, 97674223, 1195524421]	false
[123,456,789]	true
[12,123,1235,567,88]	false

 

입출력 예 설명

 

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

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

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

 

 

접근 방법

1.  한 단어가 다른 단어의 접두사가 되기 위해서는 다른 단어보다 길이가 짧거나 같아야한다.

2.  String 클래스의 index() 함수를 사용해서 0인 경우 false 그 외 true 를 반환한다.

 

문제를 처음 접할 때 위 두 가지 접근 방법을 생각해내었지만 효율성 부분에서 실패할 것을 예상하였지만 성공하였다. 그리 어렵지 않았다.

 

 

코드

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book, new Comparator<String>(){
           @Override
            public int compare(String str1, String str2){
                return str1.length() - str2.length();
            }
        });
        
        for(String num : phone_book){
            System.out.print(num +" ");
        }
        for(int i=0;i<phone_book.length-1;i++){
            String str = phone_book[i];
            for(int j=i+1;j<phone_book.length;j++){
                if(phone_book[j].indexOf(str) == 0){
                    return false;
                }
            }
        }
        return true;
    }
}

 

느낀점

 

이중 for문을 사용하기 때문에 O(n^2) 시간이 걸림에도 불구하고 통과되는 것을 보면 그리 좋은 문제는 아닌 듯 하다.

다른 사람들의 풀이를 보니 startsWith() 메소드를 사용 하던데 기억해야겠다.

 

위 접근 방법에서 길이에 따라 배열을 정렬하였다. 하지만 생각해보니 사전식 정렬도 가능할 것 같다.

왜냐하면 다른 단어의 접두사인 단어는 반드시 다른 단어보다 길이가 짧을 것이며, 앞부분은 동일하기 때문에 다른 단어가 사전식으로 뒤에 위치할 것이기 때문이다.

 

예를 들어, 

접두사가 될 단어를 "123"이라 가정할 때, 접두사를 가지는 단어는 "123xxxx"가 될 것이다.

길이가 3인 단어에서 "123"을 접두사로 가지는 단어는 "123"만 존재한다.

길이가 4인 단어에서 "123"을 접두사로 가지는 단어를 사전식으로 나타내면 "1231", "1232" .... 가 될 것이다.

 

"123"과 "1231" 두 수를 사전식으로 비교하면 반드시 "123"이 앞에 위치하기 때문에 숫자의 길이를 바탕으로한 정렬이 아닌 사전식 정렬을 통해서도 위 문제를 해결할 수 있을 것이다.