728x90
🔗 745. Prefix and Suffix Search
📌오늘의 학습 키워드
- 오늘 갑자기 난이도가 높아졌다. 시간 초과 문제를 잘 다뤄야 했는데 역시 hash(dictionary)로 해결했다.
✨공부한 내용 본인의 언어로 정리하기
- 각각의 항목을 직접 확인하기 보다는 모든 경우의 수를 dictionary 에 두고 마지막에 확인해야 시간 초과가 일어나지 않았다.
📚오늘의 회고
- 어떤 문제가 있었고, 나는 어떤 시도를 했는지
- 단순하게 for문에서 startswith, endswith로 확인하려고 했으나 실패했다.
- 어떻게 해결했는지
- 가능한 prefix, suffix dictionary를 다 만들어 놓고 거기에서 찾았다.
- 무엇을 새롭게 알았는지
- 마지막에 검색하기보다 모든 경우의 수를 만들어 놓고 검색하는게 더 빠를 수 있구나!
[🤓문제 해결 코드]
class WordFilter:
def __init__(self, words):
self.words = words
self.dict = {}
for idx, w in enumerate(words):
for i in range(len(w) + 1):
for j in range(len(w) - 1, -1, -1):
if w[:i] and w[j:]:
self.dict[w[:i] + "|" + w[j:]] = idx
def f(self, pref: str, suff: str):
if (pref + "|" + suff) not in self.dict:
return -1
return self.dict[pref + "|" + suff]
728x90
'TIL' 카테고리의 다른 글
99클럽 코테 스터디 17일차 TIL + list, hash(Dict) 메모리 초과 (0) | 2024.08.07 |
---|---|
99클럽 코테 스터디 16일차 TIL + hash(Dict) (0) | 2024.08.07 |
99클럽 코테 스터디 14일차 TIL + hash(Dict) (0) | 2024.08.04 |
[코드트리 조별과제] 아름다운 수 (0) | 2024.08.04 |
99클럽 코테 스터디 13일차 TIL + hash(Dict) (0) | 2024.08.03 |