https://school.programmers.co.kr/learn/courses/30/lessons/42577
해시는 데이터를 빠르게 넣거나 가져올 때 사용하는 기법이다. 실행 시간을 단축하고, 실행을 효율화하기 위해 해시 자료구조를 사용한다.
만약 본 문제에 리스트를 사용한다면 효율성 테스트를 통과할 수 없다.
def solution(phone_book):
answer = True
hash = {}
# 해시 테이블 만들기
for i in phone_book:
hash[i] = 1
# phone_book 배열의 번호들을 하나씩 조회(i)함
# 조회한 숫자(i)를 첫 글자부터 한 글자씩 추가해가면서 hash 테이블에 같은 번호가 있는지 조회함
# 본인 숫자의 접두사가 되는 숫자가 있는지 조회함
for i in phone_book:
temp = ''
for j in i:
temp += j
# 해당 숫자의 일부분인 temp와 동일한 숫자가 hash에 있으면, 그 숫자가 접두가사 됨
# 단, 그 숫자가 자기자신인 경우는 제외 ("119"는 "119"의 접두사가 아님)
if temp in hash and temp != i:
answer = False
return answer
코드 실행 결과
위 아이디어로 코드를 구현할 때 꼭 hash를 사용해야 하는지 궁금했다. 딕셔너리를 생성하지 않고 주어진phone_book 배열을 이용해 해당 배열의 요소들을 하나씩 탐색하면서 접두사 관계인 번호가 있는지 찾아보았다.
그 결과 시간 초과가 나타나며 효율성 점수를 받지 못했다. 코드의 효율화를 위해 가능하다면 무조건 딕셔너리와 해시 자료구조를 사용해야 겠다.
def solution(phone_book):
answer = True
for p in phone_book:
tmp = ''
for i in p:
if tmp in phone_book and tmp != p:
answer = False
break
tmp += i
return answer
코드 실행 결과
- 해시 자료구조와 딕셔너리를 사용한 방식에 비해 실행 시간이 굉장히 오래 걸리는 모습을 볼 수 있다.