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

SeokHyun·2022년 7월 11일
0

프로그래머스

목록 보기
22/32

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42577

문제 접근

맨처음에는 조합으로 뽑아서 길이가 짧은게 긴 거의 시작인가를 검사했다 (효율성 검사 시간 초과)

문자열 길이로 정렬 후, 2중 for문으로 검사 (효율성 검사 시간 초과)

위의 경우는 모두 O(n^2)이다.

핵심

  1. 문자열 배열 정렬의 원리를 이용해야함
    • 문자열 정렬은 앞에 문자를 기준으로 정렬됨(숫자의 크기가 아님)
  2. 정렬된 문자열 배열의 경우 ii+1만 비교하면됨

위와 같이 수행할 시 , O(n)으로 수행 가능

소스 코드

from itertools import combinations

def solution(phone_book):
    sortedPhone = sorted(phone_book)
    
    for i in range(0, len(sortedPhone) - 1):
        p1 = sortedPhone[i]
        p2 = sortedPhone[i + 1]
        
        if p2.startswith(p1):
            return False
    
    return True
profile
SI를 넘어 백엔드 엔지니어를 향하여

0개의 댓글