🐒 문제
https://programmers.co.kr/learn/courses/30/lessons/42577
✍ 나의 풀이
def solution(phone_book):
dic = set(phone_book)
for i in dic:
tmp = ''
for j in i:
tmp += j
if tmp in dic and tmp != i:
return False
return True해시 카테고리의 문제를 풀었다.
접근방법을 제대로 떠올리지 못하고 검색을 했다.
참고한 블로그 https://coding-grandpa.tistory.com/86
🧠 문제 이해
한 번호가 다른 번호의 접두어이면 False를 반환하고 아니면 True를 반환
예 : ['123', '12']일때 '12'는 '123'의 접두어 이므로 False 반환
첫번째 코드 (시간초과)
def solution(phone_book):
for idx1, val in enumerate(phone_book):
for idx2, num in enumerate(phone_book):
if idx1 == idx2:
break
if val.startswith(num):
return False
if num.startswith(val):
return False
return True정확성 테스트
테스트 1 〉 통과 (0.01ms, 10.3MB)
테스트 2 〉 통과 (0.01ms, 10.2MB)
테스트 3 〉 통과 (0.01ms, 10.1MB)
테스트 4 〉 통과 (0.01ms, 10.1MB)
테스트 5 〉 통과 (0.01ms, 10.1MB)
테스트 6 〉 통과 (0.00ms, 10.1MB)
테스트 7 〉 통과 (0.00ms, 9.99MB)
테스트 8 〉 통과 (0.01ms, 10MB)
테스트 9 〉 통과 (0.00ms, 10.1MB)
테스트 10 〉 통과 (0.00ms, 10.1MB)
테스트 11 〉 통과 (0.01ms, 10.1MB)
테스트 12 〉 통과 (0.00ms, 10.2MB)
테스트 13 〉 통과 (0.00ms, 10.1MB)
테스트 14 〉 통과 (103.95ms, 10.2MB)
테스트 15 〉 통과 (187.32ms, 10.1MB)
테스트 16 〉 통과 (302.91ms, 10.3MB)
테스트 17 〉 통과 (431.91ms, 10.3MB)
테스트 18 〉 통과 (626.16ms, 10.2MB)
테스트 19 〉 통과 (606.47ms, 10.3MB)
테스트 20 〉 통과 (910.44ms, 10.4MB)
효율성 테스트
테스트 1 〉 통과 (0.02ms, 10.8MB)
테스트 2 〉 통과 (0.02ms, 10.8MB)
테스트 3 〉 실패 (시간 초과)
테스트 4 〉 실패 (시간 초과)단순히 이중 for문으로 코드를 짜봐야겠다하고 덤볐는데 막상 구현할 방법이 안떠올라서 검색을 했다.
s.startswith(v) 는 문자열s가 문자열v로 시작하는지(접두어인지)를 boolean으로 리턴하는 메소드이다.
단순하게 생각해보면 이중for문이면 O(n^2)일테니 시간 초과에 걸린듯.
그렇다면 O(n^2)보다 빠르게, linear search로 작동할 수 있을까?
두번째 코드 (성공)
def solution(phone_book):
dic = set(phone_book) # 딕셔너리로 만들려다가 value가 필요없어서 set로 만듬
for num in dic: # dic을 돌면서 숫자 하나 꺼냄
tmp = '' # 접두어를 저장할 변수 초기화
for i in num: # 숫자 앞에서부터 하나씩 꺼내면서
tmp += i # tmp에 접두어로 붙이기
if tmp in dic and tmp != num: # 접두어가 dic에 있고, 찾은 숫자가 접두어 그 자체가 아니면 탐색성공
return False
return True정확성 테스트
테스트 1 〉 통과 (0.01ms, 10.1MB)
테스트 2 〉 통과 (0.01ms, 10.1MB)
테스트 3 〉 통과 (0.01ms, 10.1MB)
테스트 4 〉 통과 (0.01ms, 10.3MB)
테스트 5 〉 통과 (0.01ms, 10.2MB)
테스트 6 〉 통과 (0.01ms, 10.1MB)
테스트 7 〉 통과 (0.01ms, 10.2MB)
테스트 8 〉 통과 (0.01ms, 10.2MB)
테스트 9 〉 통과 (0.01ms, 10.3MB)
테스트 10 〉 통과 (0.01ms, 10.3MB)
테스트 11 〉 통과 (0.01ms, 10.2MB)
테스트 12 〉 통과 (0.01ms, 10.2MB)
테스트 13 〉 통과 (0.01ms, 10.2MB)
테스트 14 〉 통과 (2.04ms, 10.2MB)
테스트 15 〉 통과 (1.49ms, 10.4MB)
테스트 16 〉 통과 (5.76ms, 10.3MB)
테스트 17 〉 통과 (6.49ms, 10.3MB)
테스트 18 〉 통과 (6.52ms, 10.3MB)
테스트 19 〉 통과 (1.10ms, 10.3MB)
테스트 20 〉 통과 (4.41ms, 10.4MB)
효율성 테스트
테스트 1 〉 통과 (0.97ms, 11.4MB)
테스트 2 〉 통과 (1.08ms, 11.2MB)
테스트 3 〉 통과 (444.18ms, 41.4MB)
테스트 4 〉 통과 (33.22ms, 39.2MB)위 코드는 검색을 통해서 찾은 코드에 내가 이해하는 과정에서 수정을 거쳤다.
예를 들어
phone_book = ['123', '12'] 일때
dic = set(phone_book)
처음에 '123'이 num에 들어오고,
tmp += '1'
tmp = '1' 인데, '1'은 dic에 없으니 넘어가고
tmp += '2'
tmp = '12' 인데, '12'가 dic에 있고, '123'의 일부분이니 조건에 만족하여 False를 리턴.
딕셔너리에서 key를 찾는데 걸리는 시간은 O(1)이므로 빠르게 동작한다.
쥐구멍에 볕드는 날