배열 안의 수가 다른 수의 접두어가 되면 False를 출력하는 문제
어렵지 않아보이는 문제라서 쉬울 것을 예상하고 코드를 시작헀다.
결과1
def solution(phone_book):
answer = True
for num in phone_book :
thisNum = num
for otherNum in phone_book :
if otherNum[:len(thisNum)] == thisNum and thisNum != otherNum :
return False
return answer뽑은 전화번호와 같은 길이로 다른 전화번호를 슬라이싱하여 비교했을때 같으면 False를 제출한다.
코드 실행을 돌려보니 통과가 나오고, 뭐야 간단하네 하면서 제출을 눌렀더니 통과통과통과통과.....어?🙄
마지막 테스트 3,4에서 시간초과가 나왔다.
효율성 뿐만 아니라 실행 결과를 봐도 마지막 테스트의 시간이 심상치 않긴하다.
위 코드에서 배열을 자꾸 선형탐색 하는 것이 원인으로 보인다. 사실 문제 자체도 해시를 쓰라는 것 같긴 하다.
이 문제를 해시테이블로 해결 해야겠다고 생각을 정리하고 어떻게 하면 구성할 수 있을지 생각을 정리했다.
처음부터 생각을 배열로 시작해서 그런지 떠올리기가 쉽지 않다.
결과2
def solution(phone_book):
answer = True
bookhash = {}
for num in phone_book : #초기 해시테이블 셋팅
bookhash[num] = 1
for num in bookhash : #전화번호 목록 꺼내와서
tempnum = ''
for n in num : #앞부터 숫자를 탐색
tempnum += n #누적으로
if bookhash.get(tempnum) and tempnum != num : #전화번호 앞부분이 해시테이블에서 검색됨, 또한 해당 전화번호가 아니여야 함
return False
return answerkey에 전화번호들을 담아두고 접두어의 존재를 해시테이블 내의 key를 조회하는 방식이다.
또한 현재 단어가 다른 단어에 접두어인지를 비교했던 방식으로는 테이블을 조회할 수 없기 때문에(할 수 있지만 다시 복잡해짐)
단어의 1,12,123... 이런식으로 테이블을 조회하고, 테이블에서 조회 될 경우
해당 해시는 현재 단어의 접두어이기 때문에 False를 제출한다.
코드를 짜보니 조건이 하나 더 추가되었다. tempnum != num으로 자기 자신이 접두어라고 할 수 있어 조건에서 제외해야 한다.
제출하고 보니 정말 놀라운 속도 차이를 보여준다!
테스트 20번 같은 경우는 속도가 무려 약 200배 차이..
이런 걸 보면 알고리즘의 중요성을 다시 한번 깨닫는다.
+)
팀원에 다른분이 startwith이라는 함수를 이용해 for문으로 조회하시는걸 보았다...
맞다 저런 함수가 있었지 😂😂😂.....
for문을 줄일 수 있어 훨씬 나은 방법으로 보인다
후기
배열은 평소 나에게 굉장히 익숙한 방식이기 때문에 모든 문제나 접근 방법을 자꾸 배열로 해결하게 된다.
이번에도 배열로 가능하니까 그냥 배열로 해버려야지~ 했다가 처참한 결과를 맛보게 되었다.😅
아무리 시험이더라도 당장 나에게 익숙한 방식으로 빠르게 구현하려고 급급해 하지 말고
해당 문제에서 어떻게하면 좀 더 최적화되고 효율성 좋은 설계를 할 수 있는지부터 고민하는 습관을 들여야겠다.
