[Programmers] Hash - 전화번호 목록 (Python)

Hash: 전화번호 목록 [Lv2]

문제 설명

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

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

phone_book|return ---|--- ["119", "97674223", "1195524421"]|False ["123","456","789"]|True ["12","123","1235","567","88"]|False

입출력 예 설명

입출력 예 #1 앞에서 설명한 예와 같습니다.
입출력 예 #2 한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.
입출력 예 #3 첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

&nbsp

<span style="color:#48AB7E">Solution</spsn>

내 풀이

def solution(phone_book):
    answer = True

    for i in range(len(phone_book) - 1):
        size = len(phone_book[i])
        for j in range(i+1, len(phone_book)):
            length = len(phone_book[j])
            if length < size and phone_book[i][:length] == phone_book[j]:
                answer = False
                break
            elif phone_book[j][:size] == phone_book[i]:
                answer = False
                break
        if not answer:
            break

    return answer

리스트에서 하나씩 비교하는 선형리스트 방식으로 풀었다. for문에서 phone_book[i]는 기준이 되고, phone_book[j]는 비교대상이 된다. phone_book[i]와 phone_book[j] 중 길이가 짧은 것을 고른 후, 그것이 긴 것의 접두어인지 확인한다. 접두어가 맞으면 answer = False한 후에 반복문을 빠져나간다.

결과

선형리스트의 한계인지 효율성테스트에서 2개의 테스트케이스가 시간초과가 났다. 해시를 안쓴게 크게 작용한듯.

&nbsp

Best Code (Hash - Dictionary)

def solution(phone_book):
    answer = True
    dic = {}

    for p in phone_book:
        dic[p] = 1

    for p in phone_book:
        tmp = ""
        for num in p:
            tmp += num
            if tmp in dic and tmp!=p:
                answer = False

    return answer

전화번호들을 딕셔너리에 모두 담은 후에 for문을 통해 탐색한다. tmp라는 빈 String을 만들고 전화번호를 한 숫자씩 담는다. 한 숫자가 담길 때마다 dic에서 tmp가 key로 존재하는지 확인(tmp in dic). tmp에 모든 전화번호가 담기면 p와 같고, 이 경우에는 tmp가 dic에 담겨져 있기 때문에 이 경우를 제외해야 한다.

해당 방법은 Hash를 적절히 잘 사용한 예인듯.

결과

&nbsp

Best Code (zip 사용)

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

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

전화번호를 순서대로 정렬하면 아래와 같이 된다. ["123", "456", "789", "1235", "756"] -> ['123', '1235', '456', '756', '789'] zip을 사용하는데 위 for문과 같이 두번째 인자를 1번 인덱스부터 슬라이싱 하게 되면 p1, p2에는 각각 연속되는 순서의 숫자가 들어간다.

ex)	p1 = "123", p2 = "1235"
	p1 = "1235", p2 = "456"

startswith() 함수를 통해 p2가 p1으로 시작하는 지 확인할 수 있고, True, False를 반환받는다.

결과

문제의 의도는 Hash를 사용하는것이기 때문에 의도대로라면 hash를 사용하는것이 맞지만, 효율성을 생각했을때는 zip과 startswith 사용하는 방법이 더 효율적으로 보인다.

startswith()

문법

str.startswith(str, strbeg=0, strend=len(string))

매개변수

str: 찾을 문자열
strbeg: 비교할 문자열의 검색 시작 위치
strend: 비교할 문자열의 검색 끝 위치