이 포스팅은 프로그래머스 시리즈 28 편 중 17 번째 글 입니다.
목차
풀이
이전에 풀었을 때는 정렬을 기반으로 풀었다. 그런데 일단 n2으로 풀면 안되더라. 그래서 일단 저번처럼 풀긴했는데, stack 풀이가 있었다.
여기서 배워야 하는 점은, 발상을 반대로 하는 것이다. 그니까 나는 작은 번호를 큰 번호에서 찾으려고 했는데, 이런 발상을 할 경우 hash를 사용할 수가 없다. 해시는 특정 값이 있는지 없는지 탐색할 때 속도가 빠른 것이기 때문에 이런 장점을 이용할 수가 없기 때문이다.
그렇기 때문에 오히려 긴 문자열에서부터 접근하는 것이 좋다. 긴 문자열에서 접두어를 늘려가면서, 그 접두어가 있는지 확인하는 것. 이러면 사용가능하다.
문제의 접근 방법에 대해 더 많이 고민해야 한다.
Code
def solution(phone_book):
hash_map = { num: 1 for num in phone_book }
for phone_num in phone_book:
word = ""
for num in phone_num:
word += num
if word in hash_map and word != phone_num:
return False
return True