해시
📝 문제
문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
- 구조대 : 119
- 박준영 : 97 674 223
- 지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
제한사항
- phone_book의 길이는 1 이상 1,000,000 이하입니다.
- 각 전화번호의 길이는 1 이상 20 이하입니다.
- 같은 전화번호가 중복해서 들어있지 않습니다.
💡 나의 풀이
def solution(phone_book):
answer = True
for i in phone_book :
l = len(i)
a = 0
for j in range(len(phone_book)) :
if i == phone_book[j][0:l] :
a += 1
if a > 1 :
answer = False
break;
return answer전화번호부의 첫 번째 원소부터 전화번호의 길이를 저장해 모든 원소와 비교해서 같은 게 1개 넘으면 접두어인 경우가 있다고 판단하는 풀이! 이 코드가 정확성 테스트는 다 통과했지만.. 효율성 테스트를 통과하지 못했다ㅜ 그래서 이 문제도 컨닝 ㅜㅜ
🔗 다른 사람의 풀이
1
def solution(phoneBook):
phoneBook = sorted(phoneBook)
for p1, p2 in zip(phoneBook, phoneBook[1:]):
if p2.startswith(p1):
return False
return True
내가 캐치하지 못했던 충격적인 사실 하나! 전화번호부를 정렬하면 바로 앞, 뒤에 있는 원소끼리만 비교하면 된다! 나는 하나의 원소를 나머지 모든 원소랑 비교하는 과정을 전화번호 갯수만큼 하다보니.. 효율성 테스트를 통과하지 못한 것 같다.
전화번호부를 정렬해주고 zip() 함수를 통해 앞, 뒤에 있는 번호를 p1, p2로 각각 지정한다. p2가 p1으로 시작하면 False 반환.
이 풀이에서 배워갈 것
zip( )
- 같은 길이의 리스트를 같은 인덱스끼리 잘라서 리스트로 반환을 해주는 역할
- 리스트의 길이가 서로 다를 경우 짧은 길이 기준으로 반환
2
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
해시 이용해서 풀기! 전화번호를 해시에 다 넣고 value=1로 설정하고 전화번호 앞에서부터 한글자씩 떼서 다른 전화번호들과 비교한다. 다른 전화번호의 접두어인 경우 False를 반환하는 방법이다.
