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

[36] 전화번호 목록

책 구매하기

문제 정보

• 분류: 집합
• 정답률: 60%
• 권장 시간 복잡도: O(N log N)
• 핵심 키워드: 정렬, 접두어, 전화번호, 인접 비교
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42577

문제를 읽을 때 체크할 포인트

모든 쌍을 비교하면 비효율적이다. 문자열을 정렬하면 접두어가 될 수 있는 번호끼리 서로 붙게 되므로, 이웃한 두 번호만 보면 된다.

연결 여부를 다시 계산하면 비효율이 커진다. 이미 같은 편인지 아닌지를 빠르게 확인할 수 있어야 하고, 그 지점에서 유니온 파인드가 바로 떠올라야 한다.

풀이 흐름

1. 전화번호 목록을 사전순으로 정렬한다.
2. 정렬된 배열에서 인접한 두 번호를 비교한다.
3. 앞 번호가 뒤 번호의 접두어면 False, 끝까지 없으면 True다.

구현할 때 놓치기 쉬운 부분

전화번호를 전부 서로 비교할 필요는 없다. 정렬한 뒤 이웃한 문자열끼리만 접두어 여부를 비교하면 된다. 모든 쌍을 비교하는 방식으로 가면 정확성은 맞아도 효율성에서 바로 막힌다.

파이썬 정답 코드

def solution(phone_book):
  # 전화번호 목록을 사전순으로 정렬한다.
  phone_book.sort()

  # 정렬된 배열에서 인접한 두 번호를 비교한다.
  for i in range(len(phone_book) - 1):
    # 앞 번호가 뒤 번호의 접두어면 False, 끝까지 없으면 True다.
    if phone_book[i + 1].startswith(phone_book[i]):
      return False

  return True

시간 복잡도

N은 phone_book의 길이이다.

핵심 비용은 정렬이다. N개 데이터를 정렬하는 데 O(N log N)이 들고, 정렬 뒤에 붙는 한 번의 순회나 해시 조회는 선형이라 전체 차수를 바꾸지 않는다.

따라서 시간 복잡도는 O(N log N)이다.