Hash: 전화번호 목록 [Lv2]
문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
- 구조대 : 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 |
입출력 예 설명
- 입출력 예 #1
앞에서 설명한 예와 같습니다. - 입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다. - 입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.
Solution
내 풀이
def solution(phone_book):
answer = True
for i in range(len(phone_book) - 1):
size = len(phone_book[i])
for j in range(i+1, len(phone_book)):
length = len(phone_book[j])
if length < size and phone_book[i][:length] == phone_book[j]:
answer = False
break
elif phone_book[j][:size] == phone_book[i]:
answer = False
break
if not answer:
break
return answer
리스트에서 하나씩 비교하는 선형리스트 방식으로 풀었다.
for문에서 phone_book[i]는 기준이 되고, phone_book[j]는 비교대상이 된다.
phone_book[i]와 phone_book[j] 중 길이가 짧은 것을 고른 후, 그것이 긴 것의 접두어인지 확인한다. 접두어가 맞으면 answer = False한 후에 반복문을 빠져나간다.
결과
선형리스트의 한계인지 효율성테스트에서 2개의 테스트케이스가 시간초과가 났다. 해시를 안쓴게 크게 작용한듯.
Best Code (Hash - Dictionary)
def solution(phone_book):
answer = True
dic = {}
for p in phone_book:
dic[p] = 1
for p in phone_book:
tmp = ""
for num in p:
tmp += num
if tmp in dic and tmp!=p:
answer = False
return answer
전화번호들을 딕셔너리에 모두 담은 후에 for문을 통해 탐색한다.
tmp라는 빈 String을 만들고 전화번호를 한 숫자씩 담는다.
한 숫자가 담길 때마다 dic에서 tmp가 key로 존재하는지 확인(tmp in dic).
tmp에 모든 전화번호가 담기면 p와 같고, 이 경우에는 tmp가 dic에 담겨져 있기 때문에 이 경우를 제외해야 한다.
해당 방법은 Hash를 적절히 잘 사용한 예인듯.
결과
Best Code (zip 사용)
def solution(phoneBook):
phoneBook = sorted(phoneBook)
for p1, p2 in zip(phoneBook, phoneBook[1:]):
if p2.startswith(p1):
return False
return True
전화번호를 순서대로 정렬하면 아래와 같이 된다.
["123", "456", "789", "1235", "756"] -> ['123', '1235', '456', '756', '789']
zip을 사용하는데 위 for문과 같이 두번째 인자를 1번 인덱스부터 슬라이싱 하게 되면
p1, p2에는 각각 연속되는 순서의 숫자가 들어간다.
ex) p1 = "123", p2 = "1235"
p1 = "1235", p2 = "456"
startswith() 함수를 통해 p2가 p1으로 시작하는 지 확인할 수 있고, True, False를 반환받는다.
결과
문제의 의도는 Hash를 사용하는것이기 때문에 의도대로라면 hash를 사용하는것이 맞지만, 효율성을 생각했을때는 zip과 startswith 사용하는 방법이 더 효율적으로 보인다.
startswith()
문법
str.startswith(str, strbeg=0, strend=len(string))
매개변수
- str: 찾을 문자열
- strbeg: 비교할 문자열의 검색 시작 위치
- strend: 비교할 문자열의 검색 끝 위치
