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

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

1. 문제 설명

1. 문자열로 된 전화번호의 접두어를 탐색하기 위해 정렬을 통해 연관된 내용을 탐색하도록 하는 것이 중요하다.

Arrays.sort(phone_book)

2. 어떤 번호와 다른 번호의 접두어 여부를 판별해야 하므로 String의 startswith 메서드를 사용해야겠다고 생각했다.

3. 해당 방식으로 문제를 접근할 경우, 시간 복잡도는 nlog(n)의 시간 복잡도를 갖는다. 그 이유는 자바에서 지원하는 Arrays.sort(Object[])는 TimSort를 사용해서 nlog(n)을 사용하기 때문이다. (Arrays.sort(int[])는 Quick Sort를 지원한다.)

TimSort

• hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds dof real-world data.
  Tim-sort(wikipedia) - 다음에 한번 별도로 학습해봐야겠다.

2. 문제 해결 코드

import java.util.Arrays;

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

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

3. Reference

• Time Comparison of Arrays.sort(Object[]) and Arrays.sort(int[])[baeldong]

• Tim-sort(wikipedia)