42577 전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

 

trial #1

- prefix가 아니라 in으로 잘못 처리했음

- 효율성 테스트 시간 초과. (이중 for문은 최악의 경우 O(n^2)의 시간복잡도.) -> startswith로 고쳐도 여전히 문제되는 부분.

def solution(phone_book):
    
    rank = sorted(phone_book, key=len)
    
    for i in range(len(rank)):
        for j in range(i+1, len(rank)):
            if rank[i] in rank[j]: # startswith으로 수정해야
                return False
            
    return True

 

 

trial#2

def solution(phone_book):
    
    hash = set()
    
    for pb in sorted(phone_book, key=len):
        for i in range(len(pb)):
            if pb[:i+1] in hash:
                return False
        else:
            hash.add(pb)
            
    return True

 

 

[개선할 점]

- 해시 문제는 dict나 set을 통하여 해결할 수 있음.

- 정렬 없이 dict에 phone number들을 넣고 각 pn마다 문자열을 늘려가며 비교하는 것도 가능.