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

내가 짠 코드

def solution(phone_book):
    phone_book = list(map(int, phone_book))
    phone_book.sort()
    phone_book = list(map(str, phone_book))
    
    for idx in range(len(phone_book)-1):
        target = phone_book.pop(0)
        for number in phone_book:
            if number[:len(target)] == target:
                return False
    return True

문제점: 하나씩 줄어들기 때문에 어느정도 속도가 나오긴 하지만, 그럼에도 불구하고 불필요한 비교를 한다.

O(n)의 반복 수행이랄까,,, 사실 n은 1씩 줄어들긴 하지만 어쨋거나 O(n)의 반복.

빠른 해결책

sort, zip, startswith를 사용한 방법

정렬을 하면 문자열이 길이는 다르더라도 시작하는 값이 비슷한 애들로 정렬해준다. 그래서 앞과 뒤만 비교해보면 되는 것이었당,,, 근데 내가 생각하기에 뭔가 헛점이 있는 것 같긴 하다.

정석(해시 사용)

1. key를 번호로 하고 value는 1로 하는 해시맵(딕셔너리) 생성

2. 전화번호를 하나씩 꺼내고(for문), 하나씩 꺼낸 번호에서 숫자를 하나씩 꺼내서 temp에 붙인다.

3. temp가 hash_map에 존재하면서(phone_book에 있는 유일한 번호이면서) 지금 꺼내온 전화번호가 아니라면 False를 반환.

* temp는 전화번호가 바뀔 때 마다 초기화.

이렇게 했을 때, 만약 작은 친구가 맨 앞에 있다면 첫번쨰 탐색은 무효긴 하지만 두번째부터는 빠르게 돌아간다. 해시가 딕셔너리 구조를 말하는 건가보다...

난 해시함수 돌리는 게 해시인줄 ㅋ

해시라는 자료구조에 대해 알아봐야겠다.