https://programmers.co.kr/learn/courses/30/lessons/42577
[내 풀이]
첫번째 풀이)
접두사의 의미를 모르고 맨 처음에 not in 과 in 을 이용해서 반복문을 돌려서 자꾸 에러가 났다.
특히 문자열이 박힌 list를 굳이 int를 만들어서 sort하려는 행위가 문제를 제대로 이해한게 아니라는 생각이 든다.
바로 string값에서 sort를 해주고 앞뒤만 비교해주는 것이 왜 정답이 될 수 있는지에 대해 생각을 못했던 것 같다.
수능수학과 같은 느낌이다. 코테 또한 문제를 잘 읽고 예시도 주니까 검증까지 생각하면서 코드 짜자.
두번째 풀이)
def solution(phone_book):
answer = True
if len(phone_book)==1:
return answer
else:
temp = sorted(phone_book)
while len(temp)>1:
head = temp.pop(0)
for i in range(len(temp)):
if head == temp[i][:len(head)]:
answer = False
break
return answer
세번째 풀이)
def solution(phone_book):
length = len(phone_book)
phone_book.sort()
for i in range(length-1):
suffix = phone_book[i]
for number in phone_book[(i+1):]:
if number[:len(suffix)] == suffix:
return False
return True
두 풀이 모두 효율성 측면에서 걸렸다.
수정 풀이)
def solution(phone_book):
phone_book.sort()
for a in range(len(phone_book)-1):
if phone_book[a] in phone_book[a+1] :
return False
return True
테케 13에서 걸림.
3, 23 과 같은 경우
3이 23에 포함되기 때문에 넘어가지만, 실제로 접두어는 아니기 때문에 문제 정답이 될 수 없음.
나 같은 경우는 오히려, 12, 384, 1249 과 같이 한 타임 뛰어있는 들어있으면 못잡지 않나?
sort의 결과물에 대한 이해도 부족
아스키 코드로 문자열의 크기가 아니라 맨 앞자리부터 소팅을 시작하기 때문에
위와 같은 리스트가 만들어 질리는 없음.
def solution(phone_book):
phone_book.sort()
for a in range(len(phone_book)-1):
if phone_book[a] == phone_book[a+1][:len(phone_book[a])] :
return False
return True
다음과 같이 in을 쓰지말고, 슬라이싱을 해줘서 같다로 조건문 걸어주면 통과
[해시를 이용한 풀이]
def solution(phone_book):
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:
return False
return True
가장 문제출제의도대로 잘 푼듯.
해시도 해시지만 temp에 number 더해가면서 접두사 파악해주는 의도도 창의적이었다.
[참고1]
zip과 startswith이라는 내장함수를 이용해서 굉장히 깔끔하게 짠 것 같다.
[참고2]
def solution(phone_book):
for i in range(len(phone_book)):
pivot = phone_book[i]
for j in range(i+1, len(phone_book)):
strlen = min(len(pivot), len(phone_book[j]))
if pivot[:strlen] == phone_book[j][:strlen]:
return False
return True
댓글에 있는 코드인데 이것도 이중반복문을 이용해서 읽기 편한 것 같다.
시간복잡도 측면으로 봤을때 앞선 코드들보다 좋지 못하다.
자료구조나 알고리즘 측면으로 시간복잡도를 줄일 수도 있겠지만,
문제를 어떻게 최소한의 리소스를 들여서 해결할지, 문제를 해결하는 아이디어 측면에서도 시간복잡도를 줄일 수도 있겠다는 생각이 들었다.
'B > Coding Test' 카테고리의 다른 글
[프로그래머스] 큐/스택 - 기능개발 (0) | 2020.12.12 |
---|---|
[프로그래머스] 큐/스택 - 주식가격 (0) | 2020.12.12 |
[프로그래머스] 해시 - 베스트앨범 (0) | 2020.12.09 |
[프로그래머스] 해시 - 위장 (0) | 2020.12.09 |
[프로그래머스] 완주하지 못한 선수 (0) | 2020.12.08 |