[PS] 99클럽 코테 스터디 5일차 TIL (전화번호 목록)

문제

문제 링크

풀이 (O(n log n))

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

문제 분류는 해시라고 나오는데.. 해시보단 배열을 정렬해 문자열 비교로 푸는 것이 훨씬 효율적으로 보인다. 이 풀이 방법의 핵심은 Arrays.sort() 로 초기 배열을 우선 정렬을 하는 것이다.

만약 정렬을 하지 않고 이중 for 문으로 풀게되면 모든 문자열을 비교할 수 밖에 없어서 O(n^2) 의 시간복잡도가 된다. 또한 String[] arr4 = {"123", "12"}; 이런 테스트 케이스 처럼 접두사가 뒤쪽에 있는 경우에도 잘못된 결과가 나온다.