[Programmers] 전화번호 목록 (Lv.2)

프로그래머스에 '전화번호 목록' 문제는 코딩테스트 고득점 Kit에 해시 카테고리에 있다.

 

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

프로그래머스

 

📚 해시 알고리즘이란?

https://amazelimi.tistory.com/30?category=990184

[Python] 해시(Hash)란 무엇인가(feat. Dictionary 자료구조) | LIM

 

🧐 내가 생각한 문제 해결 순서

1. 길이 순서대로 정렬
>> 리스트를 순회하면서 해당 숫자로 시작되는 전화번호를 찾았을 때 바로 False를 리턴하기 위해서, 이렇게 할 때 길이가 짧은 전화번호가 앞에 있을수록 더 빨리 찾을 수 있다. 따라서 정렬 먼저 해두고 시작

2. 내가 찾고있는 숫자의 길이만큼 모든 전화번호를 slice 해서 사전처럼 만들기

   collections 라이브러이에 Counter 를 이용

Input: ["12", "123", "1235", "567", "88"]

찾는 전화번호: 12

결과: {"12":3,"56":1,"88":1}

Counter의 most_common(1) 을 이용해서 가장 많이 나온 전화번호를 찾고, 그 전화번호 개수가 1 이상이면 접두어가 포함되어 있다고 판단 -> False 리턴

 

위와 같이 구현했을 때

from collections import Counter
def solution(phone_book):
    length_list = sorted(list(set([len(phone) for phone in phone_book])))
    
    for length in length_list:
        slice_phone = Counter([phone[:length] for phone in phone_book]).most_common(1)
        if slice_phone[0][1] != 1:
            return False
    return True

 

 

효율성까지 모두 통과했는데 Test11, Test14 케이스가 계속 실패했다. 

 

질문하기에 들어가서 사람들이 올린 글을 찾아보니 원인을 알 수 있었다.

 

---

📌 찾는 길이만큼 자르면서 새로운 접두어를 만들지 않았는지 체크하는 로직 넣기

이게 무슨 말인지 예제를 통해 더 살펴보면

Input: ["119", "114", "112", "123223123", "1231231234"]

찾는 전화번호: '119'

결과: {"112":1,"114":1,"119":1,"123":2}

보다시피 '119' 에 대해서는 '119'로 시작하는 전화번호가 없지만, '123223123', '1231231234' 이 두 전화번호가 119 의 길이인 3만큼 자르면서 서로의 접두어로 인식(?)되게 된다.

 

따라서 Counter로 사전 만들고 most_common의 첫번째 전화번호 개수가 1이상이면 False를 Return 하는 나의 로직은 오류가 발생하게 되는 것이다.

 

따라서 내가 찾고자 하는 전화번호의 접두어 개수가 1인지 1이상인지 확인해야한다.

 

따라서 코드를 다음과 같이 수정했다.

from collections import Counter

def solution(phone_book):
    length_list = sorted(list(set([len(phone) for phone in phone_book])))

    for length in length_list:
        slice_phone = Counter([phone[:length] for phone in phone_book]).most_common(1)
        if slice_phone[0][1] != 1 and slice_phone[0][0] in phone_book:
            return False
    return True

✔ most_common(1)의 전화번호 개수가 1이 아닌지 확인

✔ 실제로 그 전화번호가 기존 전화번호북 안에 있는 번호인지 확인