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

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

1. 시간복잡도 계산하기

phone_number의 길이는 1~1,000,000이다.

즉. 내가 풀어야할 알고리즘의 시간복잡도는 n,nlogn 의 시간복잡도를 가져야 한다 n^2은 안된다.

2. 문제를 간단히 하기

접두어라는 말이 굉장히 낯설었다.

이 말은 아무 한 번호가 다른 전화번호의 시작부터 일부와 동일하면 False

서로 연관이 없으면 True

해결코드

def solution(phone_book):
    # 해시테이블 생성
    hash_table = {}
    # phone_book을 해시화
    for char in phone_book:
        hash_table[char] = 1
    # 모든 원소를 체크
    for cur_char in phone_book:
        # 접두어 선언
        jubdoo = ""
        # 해당 문자의 접두어 체크
        for cur_num in cur_char:
            jubdoo += cur_num
            if jubdoo in hash_table and jubdoo != cur_char:
                return False
        
    return True

 

해시테이블에 phone_book을 전부 입력해놓고.

phone_book의 원소의 접두어를 확인해서 문제를 해결하였다.