[Python] 프로그래머스. 2020 카카오 recruit - 가사 검색 (Level 4)

https://programmers.co.kr/learn/courses/30/lessons/60060

코딩테스트 연습 - 가사 검색 | 프로그래머스

 

 

트라이 자료구조를 안 쓰고 푸는 법 / 트라이 사용해서 푸는 법 두 가지 다 시도해 봤다.

 

트라이를 안 쓰는 경우는 python string의 startswith, endswith 방법을 사용해서 풀 수 있지만, 효율성에서 통과를 못 한다.

 

트라이를 사용할 경우 이 문제에서 가장 어려웠던 건 '문자열 개수'를 반영하는 것이었다.

fro??일 경우 fro로 시작하면서 length가 5인, fro???는 length가 6인 걸 반환해야 하는데

fro까지 도착한 뒤, 아래 노드를 전부 순회하면 시간초과가 났다. 아마 노드를 순회하는 내 코드가 비효율적이어서 그런 것 같기도 한데..

 

내가 생각한 해결방법은, 매 노드마다 length라는 dict 변수를 두고, length 값만큼 더해주는 방식이었다. 즉 '문자열의 길이가 K이면서 해당 노드를 거쳐가는 문자열의 개수'를 생성하는 방식이다.

 

예컨대 frode를 입력받아 트라이에 저장할 때, o 노드에서 노드의 length 변수는 key 5 -> value 1을 가지고 있다.

front가 입력으로 들어오면, o 노드의 length 변수는 key 5 -> value 2로 업데이트된다.

 

결과적으로, prefix까지 도달한 다음 해당 노드의 length 변수에서 문자열 길이를 key값으로 입력해서 값을 반환받는 형태로 만들었다.

 

<문자열 함수를 사용한 solution>

 

 

<트라이 자료구조를 사용한 solution>

 

 

효율성 테스트 메모리 1.32GB.....

분명 더 효율적인 방식이 있지 않을까..?