https://school.programmers.co.kr/learn/courses/30/lessons/42577
def solution(phone_book):
answer = True
phone_book.sort()
print(phone_book)
for i in range(len(phone_book)-1):
if phone_book[i] == phone_book[i+1][:len(phone_book[i])]:
answer = False
return answer
1) phone_book을 sort해준다.
2) phone_book[i]와 phone_book[i+1]을 비교하는데, 이때 phone_book의 길이만큼만 비교해준다.
3) 같으면 F, 다르면 T 반환
처음에 어떻게 접두사만 비교할지 몰라서 고민을 많이 했다.
근데 이건 Hash 분류의 문제다. Hash로 해결한 풀이를 보자.
def solution(phone_book):
answer = True
hash_map = {}
for phone_number in phone_book:
hash_map[phone_number] = 1
for phone_number in phone_book:
temp = ""
for number in phone_number:
temp += number
if temp in hash_map and temp != phone_number:
answer = False
return answer
solution(["12","123","1235","567","88"])
hash_map
이라는 딕셔너리를 생성, 이 딕셔너리는 전화번호를 키로 가지며, 해당 전화번호가 phone_book에 존재함을 나타내기 위해 모든 키의 값은 1로 설정한다.
다음으로, 각 전화번호를 다시 순회하면서 각 숫자를 하나씩 추가하여 temp 문자열을 생성한다. 이렇게 하면 temp는 phone_number의 접두사들을 차례대로 생성할 수 있다.
이제 temp
문자열이 hash_map
딕셔너리의 키 중 하나인지 확인한다. 만약 temp
가 딕셔너리의 키 중 하나라면, 그것은 temp
가 다른 전화번호의 접두사임을 의미함.
그러나 자기 자신은 자기 자신의 접두사라고 할 수 없으므로, 마지막으로 현재 검사하는 전화번호(phone_number
)와 temp가 같은지 확인한다.
만약 temp와 phone_number가 같다면, 그것은 단순히 현재 검사하는 번호 자체인 경우이므로 무시하고 계속 진행한다.
그러나 만약 temp와 phone_number가 다르다면, 그것은 현재 검사하는 번호(phone_number
) 외에도 다른 번호에서 사용되는 접두어(temp
) 가 있다는 것을 의미하므로 answer를 False 로 설정하고 루프에서 벗어남.
ㅋㅋㅋ