[PG] 전화번호 목록 JAVA

programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

전화번호 목록이 담긴 String[] phone_book이 주어진다.

등록된 번호들 중 다른 번호의 접두어로서 존재하는 번호가 있는지 찾는 문제.
(접두어가 존재하면 false, 존재하지 않으면 true를 반환. 반대여야 하는 거 아닌가..?)

 

 

풀이 1.

import java.util.Arrays;
import java.util.Comparator;

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public boolean solution(String[] phone_book) {
        // String의 길이순으로 정렬
        Arrays.sort(phone_book, Comparator.comparing(String::length));

        // O(n^2) 시간 소요..
        for(int i = 0; i < phone_book.length - 1; i++) {
            for(int j = i + 1; j < phone_book.length; j++) {
                // charAt()으로 하나씩 검사하지 않고 substring으로 한 번에 처리
                int len = phone_book[i].length();
                String sub = phone_book[j].substring(0, len);
                if (phone_book[i].equals(sub)) {  // 접두어 존재
                    return false;  // 존재'할' 경우에 false 반환임. 헷갈림 주의
                }
            }
        }
        return true;
    }
}

String[] phone_boo의 최대길이는 1,000,000 (10^6)이기 때문에 O(n^2)의 방식으로는 시간초과가 나야한다.

근데 안 나길래 그냥 O(n^2)로 풀었다. (테스트케이스가 좀 허술한 듯) 더 효율적인 방법을 모르겠다.

 

그냥 Arrays.sort()를 사용할 경우 String의 길이 순으로 정렬할 수 없었다.

구글링을 통해 Arrays.sort()의 두번째 파라미터를 찾아 길이순으로 정렬할 수 있었다.

 

처음엔 charAt()를 통해 phone_book[i].length()만큼 반복하며 [i]와 [j]의 char를 하나씩 비교하려고 했었다.

 

그 후 substring()을 통해 시간복잡도를 줄일 수 있었다. (그래봤자 O(n^2)이지만..)

 

 

 

풀이 2.

class Solution {
    public boolean solution(String[] phoneBook) {
       for(int i=0; i<phoneBook.length-1; i++) {
            for(int j=i+1; j<phoneBook.length; j++) {
                if(phoneBook[i].startsWith(phoneBook[j])) {return false;}
                if(phoneBook[j].startsWith(phoneBook[i])) {return false;}
            }
        }
        return true;
    }
}

프로그래머스의 '다른 사람의 풀이'를 통해 startWith()에 대해 알게 되었다.

시간복잡도는 동일하지만 길이순으로 정렬할 필요도 없고 코드도 더 직관적이다.