전화번호에 적힌 전화번호 중,
한 번호가 다른 번호의 접두어인 경우가 있는지 확인해야 함
접두어이면 False, 아니면 True
전화번호부에 적힌 전화번호를 담은 배열phone_book이
solution 함수의 매개 변수로 주어질 때,
어떤 번호가 다른 번호의 접두어인 경우가 있으면 False를
그렇지 않으면 True를 return 하도록 solution 함수를 작성해 주세요.
: 왜 하필이면 전화번호 목록이지? 접두어가 있는지 확인할 일이 뭐가 있지..
비교할 첫 번째 전화번호를 선택하고,
비교할 두 번째 전화번호를 선택하고,
startswith 함수를 사용해 서로가 서로의 접두어인지 확인한다.
def solution(phone_book):
# 1. Sort the phone book
for i in range(len(phone_book)):
# 2. Compare the current phone number with the next phone number
for j in range(i + 1, len(phone_book)):
# 3. If the next phone number starts with the current phone number, return False
if phone_book[i].startswith(phone_book[j]):
return False
if phone_book[j].startswith(phone_book[i]):
return False
return True
print(solution(["12", "213", "1232"]))False
그런데 이렇게 짜면 시간이.. 초과된다!
번호가 많을 때는 .........
줄이는 방법은 Sort를 활용하는 것.
이중 루프를 한 번으로 줄이기만 해도 훨씬 줄어들고.
단방향으로만 확인하면서 서로 접두어인지 확인할 수 있다면 더 줄어든다.
def solution(phone_book):
# 1. Sort the phone book
phone_book.sort()
# 2. Compare the current phone number with the next phone number
for i in range(len(phone_book) - 1):
# 3. If the next phone number starts with the current phone number, return False
if phone_book[i] == phone_book[i + 1][:len(phone_book[i])]:
return False
return True
print(solution(["12", "2132", "1232"]))False
zip을 사용해보자!
def solution(phone_book):
# 1. Sort the phone book
phone_book.sort()
print(phone_book)
print(phone_book[1:])
print(list(zip(phone_book, phone_book[1:])))
# 2. Compare the current phone number with the next phone number
for p1, p2 in zip(phone_book, phone_book[1:]):
# 3. If the next phone number starts with the current phone number, return False
if p2.startswith(p1):
return False
return True
print(solution(["12", "2132", "1232"]))['12', '1232', '2132']
['1232', '2132']
[('12', '1232'), ('1232', '2132')]
False
Hash
Key와 Value로 만들어 보자
Key = phone_number
Value = 1을 갖는 Hash map을 만들어 준다.
| Key | Value |
| "12" | 1 |
| "6789" | 1 |
| "6" | 1 |
각 번호의 접두어가 Hash map에 존재하는지 확인한다.
접두어를 찾아야 하기 때문에, 기존 전화번호의 일부를 Hash map에서 찾으면 된다.
def solution(phone_book):
# 1. Make a hash map
hash_map = {}
for phone_number in phone_book:
hash_map[phone_number] = 1
# 2. Compare the current phone number with the next phone number
for phone_number in phone_book:
prefix = ""
for number in phone_number:
prefix += number
if prefix in hash_map and prefix != phone_number:
return False
return True
print(solution(["12", "2132", "1232"]))False
