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

전화번호 목록

작성코드

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        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]) || phone_book[j].startsWith(phone_book[i])){
                    return false;
                }   
            }
        } 
        return answer;
    }
}

접근 방법

해당 문제는 전화번호부에 담긴 번호 중 다른 번호의 접두어인 경우 true를 반환하고, 아니면 false를 반환해야하기 때문에 2중 for문이 바로 떠올랐다.

하지만 전화번호부의 길이는 최대 1,000,000이어서 시간복잡도 O(n^2)경우 시간초과가 발생할 것이라고 생각했지만.. 다른 접근 방법이 떠오르지 않았다..

역시나 정확성 테스트는 통과했지만 효율성 테스트에서 모두 시간초과가 나왔다...

해결코드

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

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        Map<String, Integer> map = new HashMap<>();
        
        for(int i = 0; i<phone_book.length; i++){
            map.put(phone_book[i], i);
        }
      
        for(int i = 0; i<phone_book.length; i++){
            for(int j = 0; j<phone_book[i].length(); j++){
                if(map.containsKey(phone_book[i].substring(0,j))){
                    return false;
                }
            }
        }
        return true;

    }
}

이전 코드는 하나의 번호에 대해서 n(전화번호부 목록)-1번 만큼 startsWith()를 통해서 확인했다.

이처럼 하나의 번호를 다른 번호와 비교하는 것이 아니라, 하나의 번호를 substring()를 이용해 n(번호 길이)-1번까지 나누어서 배열에 포함되는지 확인해보기로 했다.

그리고 이때 substring()한 문자열이 전화번호부에 포함되는지 확인하기 위해 HashMap을 사용하였다.

이처럼 성공 코드는 2번 째 for문에서 n번만큼 반복하는 것이 아니라 전화번호의 최대길이 20이므로 O(20n)이 되어서 시간초과 문제를 해결할 수 있었다.