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

42577 전화번호 목록

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.

• 각 전화번호의 길이는 1 이상 20 이하입니다.

• 같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예

입출력 예 설명

입출력 예 #1

• 앞에서 설명한 예와 같습니다.

입출력 예 #2

• 한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3

• 첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

🎯 풀이 과정

1. phone_number 순서대로 돌면서 접두사인지 확인

def solution(phone_book):
    phone_book.sort()

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

    return True

다른 사람 풀이

문제가 해시 문제인데, 해시 안쓰고 풀었다 . .

어떻게 해시로 풀어야 하는지 감도 안와서 일단 다른 방식으로 풀고 다른 개발자 분들의 해시 풀이 코드를 참고했다.

def solution2(phone_book):
    hashDict = {}

    for number in phone_book:
        hashDict[number] = 1

    for number in phone_book:
        temp = ''

        for num in number:
            temp += num

            if temp in hashDict and temp != number:
                return False

    return True

1. hashDict에 폰 번호 담기
2. for문을 돌면서, hashDict에 있는지 파악하고 본인 번호인지도 파악
3. 접두사 번호가 있으면 False, 없으면 True

해시란?

• 데이터를 다루는 기법 중 하나

• 검색과 저장이 매우 빠르다

• key - value

• key 값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도는 O(1)