출처: 프로그래머스 코딩테스트 연습 전화번호 목록

전화번호 목록

나의 풀이

from itertools import combinations
import re

def solution(phone_book):
    for i in combinations(phone_book, 2):
        if re.match("^"+i[0], i[1]) or re.match("^"+i[1], i[0]):
            return False
    return True

정규표현식과 itertools의 combinations를 사용한 방식이다. 사실 시간 복잡도 때문에 효율성 측면에서 아슬아슬하게 통과된 답변이다. 간단해보이지만 좋아보이지도 않는다.

다른 사람의 풀이

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

정석대로 푼 답안이라 생각하여 가져온 풀이이다. 해쉬 카테고리에 분류된 문제로 해쉬를 이용해서 푼 답안이다. dictionary를 이용한 것은 dictionary는 해쉬 값을 이용하는 자료구조이기 때문이다. 우선 phone_book을 dictionary 형태로 바꾸어 해쉬를 통해 참조하도록 한다. 이 때 list와 같은 자료구조를 참조할 때보다 빠른 속도로 참조할 수 있다.