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

해시를 이용한 전화번호 목록 문제 풀이

프로그래머스의 전화번호 목록 문제는 주어진 전화번호 리스트 내에서 한 번호가 다른 번호의 접두사인 경우가 있는지 판별하는 문제입니다. 이번 포스트에서는 해시 테이블을 이용한 풀이 방법을 소개합니다.

---

문제 개요

• 문제 설명:
  전화번호 목록이 주어질 때, 한 번호가 다른 번호의 접두사(prefix)가 되는 경우가 있으면 False, 그렇지 않으면 True를 반환합니다.

• 접근 방식:
  모든 전화번호를 해시 테이블에 저장한 후, 각 번호의 모든 접두사를 하나씩 확인하여 해시 테이블에 존재하는지 검사합니다. 단, 자기 자신과 비교하는 경우는 제외합니다.

---

풀이 과정

1. 해시 테이블 생성:

   • 전화번호 목록의 각 번호를 키로 하여 해시 테이블에 저장합니다.

2. 접두사 탐색:

   • 전화번호 리스트에서 각 번호에 대해 한 글자씩 추가하며 접두사를 구성합니다.
   • 구성된 접두사가 해시 테이블에 존재하고, 전체 번호와 다르다면 해당 번호는 다른 번호의 접두사임을 의미합니다.

3. 결과 반환:

   • 접두사 조건을 만족하는 경우 False를, 그렇지 않으면 True를 반환합니다.

---

코드 구현

def solution(phone_book):
    answer = True
    # 해시테이블 생성
    hashmap = {}
    # 해시테이블에 값 추가하기
    for st in phone_book:
        hashmap[st] = 1
    # phone_book에 있는 값 꺼내서 탐색하기.
    for st in phone_book:
        # 한 글자씩 추가하며 확인 (st와 동일한 경우 제외)
        start_num = ""
        for st_r in st:
            start_num += st_r
            # 접두사가 해시테이블에 존재하고, 전체 번호와 다르면 접두사로 판정
            if start_num in hashmap and start_num != st:
                answer = False
                return answer
    return answer