문제
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
제한 조건
- phone_book의 길이는 1 이상 1,000,000 이하입니다.
- 각 전화번호의 길이는 1 이상 20 이하입니다.
- 같은 전화번호가 중복해서 들어있지 않습니다.
입출력 예
| phone_book | return |
|---|---|
| ["119", "97674223", "1195524421"] | false |
| ["123","456","789"] | true |
| ["12","123","1235","567","88"] | false |
풀이
def solution(phone_book):
answer = True
phone_book.sort()
if len(phone_book) == 1:
return answer
else:
while answer == True:
for i in range(len(phone_book)-1):
if phone_book[i] in phone_book[i+1][:len(phone_book[i])]:
answer = False
break
break
return answer처음에는 아래처럼 풀었는데
13번 테스트케이스가 통과되지 않았다.
["45","43456"] 이렇게 접두사가 아닌 단순 포함되는 경우에도 False를 반환하기 때문에 위에처럼 시작 바꿨다
def solution(phone_book):
answer = True
phone_book.sort()
if len(phone_book) == 1:
return answer
else:
while answer == True:
for i in range(len(phone_book)-1):
if phone_book[i] in phone_book[i+1]:
answer = False
break
break
return answer다른 풀이
해시를 이용한 다른 풀이
def solution(phone_book):
answer = True
hash_map = {}
temp = ''
#phone_book의 각 번호를 key로, 1을 values로
for phone_num in phone_book:
hash_map[phone_num] = 1
#한 글자씩 잘라서 hash_map에 존재하면(존재하면서 자기 자신은 아니어야한다.) False
for phone_num in phone_book:
temp = ''
for k in phone_num:
temp += k
if temp in hash_map and temp != phone_num:
answer = False
return answer💡TIL
Hash Table - key에 value를 저장하는 데이터 구조
- key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빠름
- key를 가지고 value를 꺼냄
- 파이썬에서는 해쉬를 단순히 딕셔너리로 구현함
왜 굳이 딕셔너리 구조(해쉬 맵)를 이용해서 구해야하나 궁금했다.
그냥 phone_book으로 찾을경우 시간초과가 나온다.
