프로그래머스 전화번호 목록(Python)

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

프로그래머스

---

문제 해결을 위한 과정

이 문제는 가장 쉽게 해결 방법을 떠올릴 수 있는 건 이중 for문이다. 그러나 이중 for문을 사용하면 phone_book의 길이는 1 이상 1,000,000 이하입니다.라는 조건 때문에 최대 1,000,000 * 1,000,000 = 1,000,000,000,000 1조 번의 연산을 수행하면 이는 시간 초과 (TLE)로 이어진다.(파이썬은 1초에 20,000,000번 연산 가) 따라서 TLE를 받지 않기 위해서는 이중 for문이 아닌, Hash를 사용하여 단일 for문으로 풀어야 함을 알 수 있다. 각각을 조회하며 각 번호가 접두사로 존재하는지 확인하고, 번호 전체를 Hash에 등록해 주면 된다. (소스코드 참고) 

단, 이때 예외케이스가 발생할 수 있는데 바로 정렬의 문제이다. ["1192345", "119"]로 phone_book이 있다면 이를 정렬하여 ["119", "1192345"]로 정렬을 한 뒤 진행해야 한다. 그렇지 않다면 위 경우는 True를 return하며 이는 오답이 될 것이다.

---

 소스코드

 

def solution(phone_book):
    answer = True
    phone_dict = {}
    phone_book.sort()
    for i in range(len(phone_book)):
        for j in range(1, len(phone_book[i]) + 1):
            if phone_book[i][:j] in phone_dict:
                return False
        if phone_book[i] not in phone_dict:
            phone_dict[phone_book[i]] = 1
        
    return answer