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

1. 문제

---

프로그래머스

 

2. 풀이 과정

---

특정 전화번호가 다른 전화번호의 접두어가 되는지를 체크하면 되는 문제이다.

 

이 문제를 가장 쉽게 해결하는 방법은 하나씩 비교하는 것이다.

phone_book[i]와 i가 아닌 다른 전화번호를 하나씩 비교하며 접두어가 되는지 체크하면 된다. 

하지만 이 문제의 함정은 입력 크기이다.

최대 100만인데 이러면 해당 방법의 시간복잡도인 O(N^2)으로는 풀기 힘들다.

따라서 더 효율적인 방법을 생각해봐야 한다. 어떻게 하면 더 효율적으로 해결할 수 있을까?

 

바로 정렬을 활용하는 것이다.

배열을 오름차순으로 정렬하게 되면 접두어가 되는 문자열이 해당 접두어를 포함하는 문자열 앞에 위치한다. 

따라서 해당 배열을 오름차순 정렬한 뒤 첫번째 인덱스부터  바로 뒤에 문자열이 현재 문자열로 시작하는지만 체크하고 시작한다면 false를 반환하면 된다.

 

이제 코드를 보자.

3. 내 코드

---

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

시간 복잡도

• O(NlogN)

정렬: O(NlogN)

뒷 문자열이 현재 문자열로 시작하는지 체크: O(N)