99클럽 코테 스터디 15일차 TIL + 완전 탐색

[오늘의 학습 키워드 및 문제]
- 리트코드의 "Prefix and Suffix Search" 문제를 풀었다.
- 완전 탐색이 주제인데 조건만 아니었으면 완전 탐색으로 안 풀어도 된다.
- 입력이 [[["apple"]],["a","e"]] 이면, apple 쪽이 단어고, a/ e 쪽이 접두사, 접미사이다. 접두사, 접미사의 길이가 서로 다를 수 있다는 건지 잘 모르겠는데 난 다를 수도 있다고 생각하고 풀었다.

[나의 코드]

# 1차 시도

class WordFilter:

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

    def f(self, pref: str, suff: str) -> int:
        idx = -1
        for i in range(len(self.words)):
            front = ''
            back = ''
            
            front += self.words[i][:len(pref)]

            temp = len(self.words[i]) - len(suff)
            back += self.words[i][temp:]

            if front == pref and back == suff:
                idx = i
        return idx

처음에 이 코드를 작성하였다. 
시간복잡도가 O(n * m)이니까 시간 초과가 뜨지 않을 줄 알았다.
근데 놓치고 있던 조건 하나가 있었다.

{At most 10^4 calls will be made to the function f}
알고 보니 최대 f 함수가 10,000번 이상 계산을 하지 않는다는 굉장히 음침한 조건이 붙어있던 것이다.
어쩐지... 내 코드는 잘못 없다.

그래서 문제의 설명에 나와있는 대로 딕셔너리에다가 집어넣어 봐야 할 것 같아서 그리 풀어 보았다. (에혀..)

# 2차 시도

class WordFilter:

    def __init__(self, words: List[str]):
        self.search = {}
        for index, word in enumerate(words):
            length = len(word)
            for i in range(length + 1):
                for j in range(length + 1):
                    prefix = word[:i]
                    suffix = word[j:]
                    self.search[prefix + '#' + suffix] = index

    def f(self, pref: str, suff: str) -> int:
        key = pref + '#' + suff
        return self.search.get(key, -1)

사진 자료를 가져와 봤다. (출처. 어느 외국인)

아래와 같이 모든 조합을 딕셔너리에다가 집어넣을 것이다.

예) word = 'leet'> leet#leet
                  eet#leet
                  et#leet
                  t#leet
                  #leet

사이트에서 제공하는 다음 예제를 예시로 딕셔너리에 집어넣으면 결과는 다음과 같다.

[[["apple"]],["a","e"]]

{'#apple': 0, '#pple': 0, '#ple': 0, '#le': 0, '#e': 0, '#': 0, 'a#apple': 0, 'a#pple': 0, 'a#ple': 0, 'a#le': 0, 'a#e': 0, 'a#': 0, 'ap#apple': 0, 'ap#pple': 0, 'ap#ple': 0, 'ap#le': 0, 'ap#e': 0, 'ap#': 0, 'app#apple': 0, 'app#pple': 0, 'app#ple': 0, 'app#le': 0, 'app#e': 0, 'app#': 0, 'appl#apple': 0, 'appl#pple': 0, 'appl#ple': 0, 'appl#le': 0, 'appl#e': 0, 'appl#': 0, 'apple#apple': 0, 'apple#pple': 0, 'apple#ple': 0, 'apple#le': 0, 'apple#e': 0, 'apple#': 0}

그리고 pref + # + suff 계산한 값이 딕셔너리 안에 있는 것을 확인할 수 있다.

---

코드는 외국인과 gpt가 준 힌트를 바탕으로 풀었다.
코드를 차근히 하나씩 설명해 보겠다.

일단 딕셔너리에 집어넣을 것이므로 딕셔너리를 하나 초기화해 준다.
enumerate 함수를 써서 for문을 돈다. 참고로 이 함수는 인덱스와 값을 포함하여 반환해 주는 함수다.

그다음 코드는 이해하기 어렵지 않을 것이다. 모든 조합을 넣어줄 것이다.
그리고 그 사이에 #를 같이 넣어서 딕셔너리에 넣어주면 된다.

마지막으로 접두사와 접미사가 일치하는 것을 딕셔너리에서 찾아 반환하면 된다.
딕셔너리의 get() 함수에 대해서 더 알아가 보자. 다른 블로그를 찾아보았다.

• get() 함수는 딕셔너리에서 key에 해당하는 value를 반환하는 함수다.
• 두 개의 매개 변수를 가질 수 있는데, 첫 번째 매개 변수는 찾고자 하는 값이고, 두 번째 매개 변수는 기본값이다.

딕셔너리는 탐색 속도가 O(1) 이므로 빠를 것이다.
그래서 이 코드를 돌리면 시간 초과 없이 통과하는 것을 알 수 있었다. 

class WordFilter:
    def __init__(self, words: List[str]):
        self.search = {}
        for i in range(len(words)):
            word = words[i] 
            length = len(word)
            for j in range(length + 1):
                for k in range(length + 1):
                    prefix = word[:j] 
                    suffix = word[k:] 
                    self.search[prefix + '#' + suffix] = i

    def f(self, pref: str, suff: str) -> int:
        key = pref + '#' + suff
        return self.search.get(key, -1)

이건 enumerate 함수를 쓰지 않고 푼 코드다.
코테에선 늘 이런 함수들이 잘 기억나지 않으니 이 코드도 숙지해 두자.
그렇게 차이는 나지 않는다.ㅎㅎ;;

[오늘의 회고]
- 오늘 문제는 조건이 악랄해서 당황했다.
- 하지만 어려운 문제를 풀 수 있어서 좋은 시간이었다. 다시 한번 풀어봐야겠다.
- 그리고 다른 함수를 이용한 풀이도 있다. 시간 초과가 뜨므로 그냥 넘어갔... 끝!