[해쉬] 프로그래머스 lv2. 전화번호 목록

문제

[프로그래머스 전화번호 목록]
주어진 전화번호 목록에서, 어떤 번호가 다른 번호의 시작번호가 되는 지를 판단해라. 시작번호를 가지는 전화번호 목록이라면 false, 반대라면 true 를 반환해라.

교훈

해쉬 테이블의 효율성

해쉬는 자료를 검색하는 데 정말 빠르다고 한다. 배열과 비슷한 역할을 하도록 해도, 키 값에 접근하는 것이라면 해시가 더 빠름을 알 수 있었다. (ex. i in list vs i in dictionary) 또한, 이것처럼 중복 검색을 위해 dictionary 자료형을 임의로 생성하는 코드 형태를 엿볼 수 있었다.

prefix 검색에 대해, ((마지막 최종코드 참고))

if prefix in dic
접두사를 찾는다고 하면 접두사인 번호를 먼저 넣고 검색해야겠다고 접근하게 되는데, 이렇게 조건을 넣게 되면 자기 자신에 대한 검색도 포함되어
무조건 접두사가 있다고 결과를 반환해버린다.
이를 막고자, 뿌리가 되는 num 과 prefix가 같지 않다는 조건을 넣음으로써 누적되는 문자가 쌓이는 prefix가 스펠의 전체를 가지고 있는 num과 같지 않아야 한다고 제한한다. 이는 오히려 접두사부터 접근하기보다는 긴 놈의 부분(일부가)이 딕셔너리 내부에 키로 존재하는지를 판단하는 관점이다.
따라서, 더 빨리 찾고 반환되도록 sorting을 len이 긴 것부터 정렬하도록 수정해보았다.

def solution(plst):
    plst.sort(key= lambda x: len(x))
    ans = True
    # print(plst)

    for i in range(0,len(plst)):
        p = plst[i]
        long = len(p)
        for j in plst[i+1:]:
            if long <= len(j):
                if j[:long] == p:
                    ans = False
                    return ans
    return ans

최종 코드

def solution(plst):
    plst.sort(key= lambda x: len(x), reverse=True)
    dic = {}
    for p in plst:
        dic[p] = 1
    ans = True
    for num in dic.keys():
        prefix = ''
        for n in num:
            prefix += n
            if prefix in dic and prefix != num:
                print(prefix, num)
                ans = False
                return ans

    return ans

[참고 블로그]

그 외

문자열에 바로 인덱스

처음에 짜려고 했던 코드랑 비슷하다. 다만, 굳이 dictionary를 쓰지 않는다.

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

    return True

[참고 블로그]

.startswith()

이 메서드는 문자열이 이걸로 시작하는 게 맞는지 판단해 불리언(True, False)으로 반환한다.

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

[참고 블로그]

해쉬 알고리즘 문제를 시작하니, 연달아 파이썬 내장 함수와 메서드로 풀리는 문제가 있었다. 이에 대한 공부가 좀 더 되면, 불필요한 구현이 줄겠다..