Cooper's devlog

[문제 링크]

 이번 문제는 전화번호 목록입니다. 문제를 간략히 말씀드리면

전화번호 목록에 접두어가 중복되는 경우가 있는지를 확인하는 문제입니다.

만약 접두어가 중복되는 전화목록이 존재한다면 false

접두어가 중복되지 않는다면 true를 반환하는 문제입니다.

[1.O(n^2) 접근법]

import java.util.*;

class Solution {
	public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);

        for (int i = 0; i < phone_book.length; i++) {
            for (int j = i + 1; j < phone_book.length; j++) {
                if(phone_book[j].startsWith(phone_book[i])) {
                    return false;
                }
            }
        }

        return true;
    }
}

[2.문제 접근 방법]

1. phone_book의 요소들을 정렬(sort) 한다.

2. 정렬한 요소들을 순회하며 접두어 일치 여부를 탐색한다.

3. 순회하는 요소들 중, 접두어가 일치하는 경우가 있다면, false를 반환한다.

4. 순회를 완료한다면 일치하는 접두어가 존재하지 않는다는 것을 의미하므로, true를 반환한다.

위와 같은 방식으로 로직을 처리할 경우, 주요 로직이 이중 반복문 이기 때문에 시간 복잡도가 O(n^2)입니다.

문제는 해결했지만 좀더 시간 복잡도면에서 효율적인 방법(nlog(n))으로 접근해보겠습니다.

[3.nlog(n) 접근법]

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);

        int index = 0;
        while(index < phone_book.length - 1) {
            if(phone_book[index + 1].startsWith(phone_book[index])) {
                return false;
            }
            index++;
        }

        return true;
    }
}

결과를 비교해보면 기존에 비해서 테스트 2번의 시간이 줄어든 것을 확인해볼 수 있습니다.

그렇다면 이렇게 로직을 바꿀 수 있는 이유는 무엇일까요?

이 로직의 숨은 핵심은 Arrays.sort()와 연관성이 있습니다.

[4.Array.sort()가 String 비교할 때]

Array.sort()으로 String을 정렬할 때는 인덱스를 순차적으로 하나씩 비교합니다.

예를 들어서) apple appple applepie 라는 String이 존재할 경우, 각각의 인덱스를 순차적으로 탐색합니다.

위와 같이 가장 앞 인덱스의 char값을 순차적으로 비교하며 값이 작을수록 앞쪽에 정렬되는 방식으로 진행됩니다.

그러므로, 해당 인덱스의 String 값의 다음 값은 접두사일 경우가 상당히 높다는 것을 알 수 있습니다.

그래서 해당 인덱스(index)를 기준으로 순차적으로 탐색해가면서 값을 비교할 수 있는 것입니다.

[5. 마치며]

 이번 시간에는 전화번호 목록 문제를 풀어보았습니다. 같은 문제를 풀어도 더욱 효율적인 접근법에 대해 고민을 하면 한층 더 머리가 따끈따근해지는 순간을 느끼실 수 있을겁니다ㅎㅎ(좋은건지는 장담 못합니다😀)