문제 링크
문제 요약
전화번호부 phone_book가 주어지고 한 번호가 다른 번호의 접두어에 해당하면 False를 리턴하면 되는 문제이다.
문제 풀이
# 정답으로 제출한 코드
def solution(phone_book):
answer = True
phone_book.sort()
for i in range(len(phone_book)-1):
if phone_book[i+1].startswith(phone_book[i]):
answer = False
return answer
return answer
# 효율성에서 시간초과가 발생한 코드
def solution(phone_book):
answer = True
phone_book.sort()
for idx in range(len(phone_book)):
num1 = phone_book[idx]
for num2 in phone_book[idx+1:]:
if num2.startswith(num1):
# 번호 중복이 없으니까
# num2가 num1으로 시작한다면,
answer = False
break
if not answer:
break
return answer📌 고려해야할 점
- 효율성 문제에서 시간 초과가 처음 발생한 코드의 경우 모든 전화번호부를 검사하는 방식으로 진행하기 때문에 시간 초과가 발생한 것 같다.
정렬했다는 사실을 잘 인지하고 있었어야 했다 🙄[예시]
phone_book = ['123', '3342', '12343']
phone_book.sort() # ['123', '12343', '3342']
위의 예시를 통해 위에서 나는 phone_book을 정렬했기 때문에 '123'을 접두어로 갖는 전화번호는 바로 '123' 뒤에 존재해야한다! 그 뒤의 전화번호는 비교할 필요 없다! 만약 접두어로 갖고 있는 전화번호가 한 개라도 존재하면, False를 반환하면 되기 때문이다.
