[프로그래머스 고득점 Kit/Java] 전화번호 목록

 

다음과 같이 풀었다.

성공 코드

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        for (int i = 0; i < phone_book.length - 1; i++) {
            String phone = phone_book[i];
            if (phone_book[i + 1].startsWith(phone)) {
                return false;
            }
        }
        return true;
    }
}

 

처음에는 아래와 같이 j의 범위를 i + 1부터 phone_book.length까지로 설정했다.

실패 코드

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        for (int i = 0; i < phone_book.length - 1; i++) {
            String phone = phone_book[i];
            for (int j = i + 1; j < phone_book.length; j++) {
                if (phone_book[j].startsWith(phone)) {
                    return false;
                }
            }
        }
        return true;
    }
}

그랬더니 정확성은 테스트는 모두 통과했는데

효율성 테스트의 테스트3, 4를 시간 초과로 통과하지 못했다.

도저히 모르겠어서 힌트를 구한 결과

 

Arrays.sort로 사전순 정렬을 했으니,

내 바로 뒤에 있는 문자열과만 비교해도

접두어인지 아닌지를 판별할 수 있다는 것을 알게 됐다.

 

따라서 j의 범위를 따로 설정하지 않고,

i번째 문자열과 i+1번째 문자열을 비교해서

i번째 문자열이 i+1번째 문자열의 접두어인지 확인했다.

 

모든 정확성 테스트와 효율성 테스트를 통과했다!