난이도 : level 2
유형 : 키-해시
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42577
문제 파악
phone_book 배열을 입력 받는다. 배열안에는 숫자형태의 문자열들이 들어있다.
만약 어떤 번호가 다른 번호의 접두어,
즉 다른 번호 앞에 포함되는 관계가 있다면 false,
그렇지 않다면 true 를 return 하는 solution 함수를 작성해야한다.
어떻게 풀 수 있을까?
우선 phone_book의 길이가 최대 1,000,000 이라고 주어져있기에 인덱스 0번째부터 전체를 비교하는 n! 방법으로는 시간초과가 뜰 것 같다.
이럴때는 리스트를 사용하는 완전탐색방법보다는 dict나 set자료형을 활용하여 원하는 값을 전체를 돌지 않고 찾는 해시 탐색 방법을 사용하면 좋다.
이 문제의 경유 key-value 쌍이 필요가 없고 key만 있는 문제라 set자료형을 사용할 것이다.
풀이 및 해답
def solution(phone_book):
# 모든 번호를 set 자료형에 넣기
phone_set = set(phone_book)
for number in phone_book:
# number의 접두어들을 하나씩 잘라보며 set에 있는 지 확인.
for i in range(1, len(number)):
prefix = number[:i] # 앞에서부터 슬라이싱하며 접두어를 생성
if prefix in phone_set: # 이 접두어가 phone_set 에 있는 번호면 return false
return False
return True 해시 탐색을 위해 set자료형 (dict도 가능함) 을 선택하고,
접두어를 앞에서부터 [:i] 로 생성해나가는 스킬이 필요했던 문제이다.
Frontend Engineers