프로그래머스 - 해쉬 - 전화번호 목록

1. 문제의 출처

 

프로그래머스 - 해쉬 - 전화번호 목록

 

programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

 

2. 코드 해답

(1) Best 해답

def solution(phone_book):
    
    answer = True
    phone_book.sort()
    
    for prefix, number in zip(phone_book, phone_book[1:]):
        if number.startswith(prefix):
            answer = False
            break
 
    return answer

 

1) for 문의 1번 사용 - 시공간복잡도 O(n) - zip메소드의 활용

 

이 문제에서는 함정이 논리는 쉬워보여도, 시공간 복잡도를 효율적으로 활용하는 것이 가장 힘듭니다. 

 

만약 매번 접두어를 저장하여 다른 요소와 비교하려고 하면, O(n²)의 구조가 되어 시간 초과로 실패하기 쉽습니다. 

 

여기서는 zip() 메소드를 활용하여 for 문을 한 번만 사용해서 O(n)으로 시공간 복잡도를 절약할 수 있습니다. 

 

비교의 예시의 알고리즘이 어떻게 되는지 아래의 사진을 통해 확인 가능하십니다. 

 

내부 논리의 예시 

 

순서를 정렬했기 때문에 위와 같이 순차적으로 비교를 하여, 접두어로 시작하는지 파악할 수 있습니다.

 

다만 이 풀이의 단점은 출제의도인 "해쉬 - Key와 Value"값을 활용하지 않았다는 점에서 감점요인은 있을 것 같습니다. 

 

(2) Hash 함수의 적용

 

def solution(phone_book):
    answer = True
    hash_map = {}
    
    for phone_number in phone_book:
        hash_map[phone_number] = 1
        ##print(hash_map)
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            ##print(temp)
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer

 

내부 논리의 예시2

 

 

이 경우 받은 리스트에서 가능한 모든 접두어의 케이스를 우선 만듭니다. Hash map이 이에 해당하는 것이죠.

 

그리고 다른 for문에서 받은 케이스별로 가능한 모든 접두어의 케이스를 계사하고, 그것이 hash map에 존재한다면 False값을 반환하도록 만들어 놓은 구조입니다. 

 

이 해답이 Key와 Value 값을 활용한 가장 바람직한 모범 해답이라고 할 수 있을 것 같습니다. 

 

 

 

정답 인증