99클럽 코테 스터디 15일차 TIL (745. Prefix and Suffix Search)

오늘의 학습 키워드:  탐색

문제: 745. Prefix and Suffix Search

https://leetcode.com/problems/prefix-and-suffix-search/description/

 

풀이

갑자기 리트코드가 나와서 당황했지만..? 풀이를 진행했다.

class형태로 구현하도록 나와서 결과를 어떻게 받을 지 궁금했지만
그냥 단순하게 클래스 안에서 함수를 구현하고 리턴만 잘 해주면 되는거였다.

 

신경쓸 부분은 접두사와 접미사가 한 단어만 주어지는건 아니라는점, 시간 제한이 있다는 점이다.

초기에 틀린 코드를 보면 다음과 같이 풀었다.

class WordFilter:

    def __init__(self, words: List[str]):
        self.word_list = words

    def f(self, pref: str, suff: str) -> int:
        l_pref = len(pref)
        l_suff = len(suff)
        max_index = -1
        for idx in range(len(self.word_list)-1,-1,-1):
            word = self.word_list[idx]
            if word[:l_pref] == pref and word[-l_suff:] == suff:
                return idx
        return -1

 

이 코드는 조회 시 O(n*l)의 복잡도를 갖는다. 조회를 하는 경우에 시간을 많이 사용한다는 의미이다.

그래서 시간 초과가 나온 경우에 조회를 많이 하는 경우를 볼 수 있었는데 (L이 매우 커진다는 의미) 이로 인해서 발생한 것 같다.

따라서 시간 초과를 방지하기 위해 클래스 초기화 시에 값들을 해시로 넣는 방법을 채택했다.

class WordFilter:

	def __init__(self, words: List[str]):

		self.pair_suffix_prefix = {}

		for index in range(len(words)):

			for j in range(len(words[index])):

				new_word1 = words[index][:j+1]

				for k in range(len(words[index])):
					new_word2 = new_word1+'.'+words[index][k:]

					self.pair_suffix_prefix[new_word2] = index


	def f(self, prefix: str, suffix: str) -> int:

		search_word = prefix+'.'+suffix

		if search_word in self.pair_suffix_prefix:
			return self.pair_suffix_prefix[search_word]
		else:
			return -1

 

조회 시 해시에서 값을 찾기 때문에 O(1)의 시간복잡도를 갖는다.

물론 초기화 시에는 시간이 더 걸리지만 조회가 많다면 효율적인 코드가 된다.

회고

git에 코드가 안올라가고 있었습니다..내 잔디..

내일 학습할 것.

SQL, Python, 독서