[파이썬] 프로그래머스 전화번호 목록 풀이

문제 확인

프로그래머스

나의 풀이

처음 풀이 : 시간 초과 발생

• 접두어의 길이는 '최대 단어 길이 -1' 까지만 가능하다.
• 길이에 따라서 접두어 후보를 나누고, 이후 비교하는 방식으로 접근하려고 했다.
  • 후보를 나누고, 비교하는 과정이 대략 $O(20 * (50000)^2)$이 되기 때문에 시간 초과가 발생했다.

# 접두어 여부 확인
# 접두어? (최대 단어 길이 -1) 까지만 접두어가 될 수 있음
# 접두어 탐색 범위 : 나보다 길이가 더 긴 단어들만 확인 가능
# 길이에 따라서, 접두어 후보를 나누고, 이후 비교하면?
from collections import defaultdict

def solution(phone_book):
    # 전화 번호 길이 확인 
    phone_len = defaultdict(list)
    for i in phone_book:
        phone_len[len(i)].append(i)
    # 접두사 여부 확인
    while phone_len:
        min_len = min(phone_len.keys())
        prefix = phone_len[min_len]
        del phone_len[min_len]
        # 20 * 5만 * 5만 = 시간 초과
        for _, phone in phone_len.items():
            for p in phone:
                for pre in prefix:
                    # 접두사면, 처음 위치에서 발견됨
                    if p[:min_len] == pre:
                        return False    
    return True

정렬을 활용한 풀이

• 문자열을 정렬하면 결국 앞자리가 같은 숫자끼리 모이게 된다.
• 나머지 숫자도 같은 지 확인하면 접두어인지 알 수 있다.

def solution(phone_book):
    answer = True
    # 문자열 정렬
    phone_book.sort()
    for i in range(len(phone_book)-1):
    	# 같은 문자(숫자) 기준으로 정렬 됐기 때문에, 앞 뒤만 비교하면 됨!
        if phone_book[i + 1][:len(phone_book[i])] == phone_book[i]:
            answer = False
            break
    return answer

Hash를 활용한 풀이

• 모든 번호를 저장해둔다.
• 각 번호를 구성하는 숫자를 앞자리부터 채워 넣으면서, 저장된 번호가 있는지 확인한다.

def solution(phone_book):
    # 번호 저장
    phone_hash = set(phone_book)
    for phone in phone_book:
        temp_num = ""
        # 앞 자리의 숫자부터 추가하면서, 저장된 번호가 있는지 확인
        for digit in phone:
            temp_num += digit
            if temp_num in phone_hash and temp_num != phone:
                return False
    return True

참고한 풀이

[프로그래머스] 전화번호 목록 _ Python 해시Lv.2