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

point
문자열의 접두어가 존재하는지 확인하는 문제. 반복을 최소화 하는 것이 관건!

생각의 흐름

풀이 1

• 처음에는 단순하게 이중 반복문을 써서 일치하는 부분을 찾으려고 했다. 반복 수행 시간을 최소화 하고자... 문자열 순서대로(1, 2, 3,...) 한 번 정렬하고 문자열의 길이가 짧은 순서대로 정렬한 후에 반복문을 실행했지만 결과는 시간 초과

풀이 2

• 반복문 사용 대신, set을 이용하여 기존의 리스트 길이보다 짧아졌는지(중복이 있는지) 확인하는 방법을 떠올렸다. 하지만 이 경우, 앞 머리 번호의 일부분만 동일한 경우도 접두어라고 판단하는 문제점이 있다. (ex. 345, 11234, 11267)

풀이 3

• 다른 사람의 풀이를 보고 startswith를 사용하면 된다는 것을 깨달았다....!(왜 생각이 안났지) 또한, 맨 처음에 문자열 순서대로 정리를 해두면 i+1 번째 번호가 i와 가장 유사한 번호가 되기 때문에 i번째 번호와 i+1번째 번호만을 비교하면 된다.
  -> 모두 비교를 할 필요는 없었다....!

풀이 1

def solution(phone_book):
    answer = True
    phone_len_book = [(phone, len(phone)) for phone in phone_book]
    phone_len_book.sort(key=lambda x: x[0])
    phone_len_book.sort(key=lambda x: x[1])
    
    i = 0
    while i < len(phone_book)-1 and answer:
        head = phone_len_book[i][0]
        head_len = phone_len_book[i][1]
        
        for phone in phone_len_book[i+1:]:
            if phone[0][:head_len] == head:
                answer = False
                break
        i += 1
    return answer

풀이 2

def solution(phone_book):
    answer = True
    phone_len = [len(phone) for phone in phone_book]
    min_len = min(phone_len)
    max_len = max(phone_len)
    phone_book_len = len(phone_book)
    
    for i in range(min_len, max_len):
        new_phones = [phone[:i] for phone in phone_book]
        if len(set(new_phones)) != phone_book_len:
            answer= False
            break
            
    return answer

풀이 3

def solution(phone_book):
    answer = True
    phone_book.sort()
    
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            answer= False
            break
            
    return answer

풀이 3을 참고해서 풀이 1을 수정한 풀이

def solution(phone_book):
    answer = True
    phone_book.sort()
    
    for i in range(len(phone_book)-1):
        if phone_book[i+1][:len(phone_book[i])] == phone_book[i]:
            answer = False
            break
            
    return answer

회고

• 반복문 쓰기 전에 꼭 비교해야 할 대상들이 무엇인지 정확하게 판단해서 반복 횟수를 줄이자!
• 접두어는 startswith로 비교하면 편함