[알고리즘 / Python] 프로그래머스 - 전화번호 목록(해시)

전화번호 목록

문제 설명

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

• 구조대 : 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

내 풀이

python이라는 언어를 공부할 겸 python을 사용해서 해당 문제를 풀기로 하였습니다. 일단 핵심은 아래와 같다고 생각했습니다.

• 한 번호가 다른 번호의 접두어인지 확인하는 과정
• 비교 시에 비교하려는 번호의 길이보다 짧은 모든 번호를 비교

그래서 다음과 같은 과정으로 해당 문제를 해결하였습니다.

1. phone_book를 오름차순으로 sort() -> 문자열 같은 경우 sort할 시에 문자열 내의 글자 하나하나의 유니코드를 기준으로 정렬하게 됩니다.
2. for문을 통해 startswith()로 비교하여 true일 시 false 리턴
3. 모든 반복문을 통과했다면 True 리턴

(1) 의 예 같은 경우

["123","1235","12","88","567"] 를 정렬하면 ["12", "123", "1235", "567", "88"] 이렇게 정렬되어 앞뒤로만 비교를 해주면 됩니다.

코드 구현부

def solution(phone_book):
    phone_book.sort()

    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False          
    return True

코드를 채점한 결과 아래와 같은 결과가 나왔다.

정확성: 83.3
효율성: 16.7
합계: 100.0 / 100.0

일단 효율성이 너무 나쁘다 생각하여 다른 사람들은 어떻게 했는지 참고해서 공부해보기로 하였습니다.

다른 사람들의 풀이

예시 1

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

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

위는 zip()이라는 함수를 사용하여 문제를 해결하였는데 zip()이라는 함수는 동일한 개수로 이루어진 자료형을 묶어 주는 역할을 하는 함수라고 합니다.

>>> zip([1,2,3], [4,5,6])
[(1, 4), (2, 5), (3, 6)]

예시 2

def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer

위의 예시는 본래 문제의 목적인 Hash를 이용해서 푼 문제인데 한번 공부해보면 좋을 것 같아 가져왔습니다.