[Lv2. 전화번호 목록] 풀이 기록

처음 제출한 답

def solution(phone_book):
    
    phone_book = sorted(phone_book, key=lambda x:x)
    p_book = phone_book.copy()

    for p in phone_book:
        del p_book[0]
        for p2 in p_book:
            if p in p2:
                return False
    return True

 

리스트가 주어지고 특정 인덱스가 다른 인덱스의 접두사가 되는 경우를 찾는 건데

최대 길이가 1,000,000 이다보니 for문을 두번 돌리면서 풀면 시간초과가 난다

그리고 점수도 83.3점이라 제대로 맞히지도 못했다..

 

그래서 하루동안 머리를 싸매다가 제미나이 힘을 좀 빌림

 

우선 포인트는,

1. Dictionary를 써야 한다.

2. 관점을 좀 다르게 봐야 한다.

 

1. Dictionary

• for문 2번은 O(n^2), Dictionary는 O(n) 
• 모든 phone_book 요소를 Dictionary에 등록

2. 관점을 다르게 보자

• 처음 풀 땐 크기가 작은 놈을 기준으로 이게 어떤 큰 놈의 접두사가 될까 ? 로 접근했는데 이 방식은 결국 배열의 모든 요소를 봐야 함
• 그래서 큰 놈을 기준으로 하나씩 쪼개면서 쪼갠 값이 리스트에 있나 ? 를 보면 됨

 

블로그를 정리하면서 생각해보니 이런 식으로 2중 for문을 돌려도 정답이 되긴 한다.

def solution(phone_book):    
    phone_book = sorted(phone_book, key=lambda x:int(x), reverse=True)
    
    for p in phone_book:
        tp = ''
        for i in range(len(p) - 1):
            tp += p[i]
            if tp in phone_book:
                return False
    return True

 

다만 효율성에서 시간 초과가 떨어진다.

 

결국 2중 for문으로는 아무리 잘 짜도 100점을 못 받는 것 같다.

 

해시로 풀어보면 다음과 같다.

• phone_book에서 하나씩 꺼내고 꺼낸 요소를 한글자씩 쪼개서 dictionary에 있는지 확인한다.
• len(p) - 1 은 자기 자신과 비교하지 않기 위해서다.

def solution(phone_book):    
    
    phone_dict = {p:True for p in phone_book}

    for p in phone_book:
        tp = ''
        for i in range(len(p) - 1):
            tp += p[i]
            if tp in phone_dict:
                return False
    return True