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

오늘의 문제 - 완전탐색

리트코드  745. Prefix and Suffix Search

단어리스트, 접두사와 접미사가 주어졌을 때, 단어리스트에서 주어진 접두사와 접미사를 가지는 단어의 가장 큰 인덱스를 출력하는 문제

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

---

내 풀이 및 접근 방식

1. 브루트포스 => 시간 초과

완전 탐색이란 일단 모든 경우의 수를 시도하는 방법으로, 여러가지 방법 중 반복문과 조건문을 이용해 모든 경우의 수를 탐색하는 브루트포스를 이용했다.

class WordFilter:

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

    def f(self, pref: str, suff: str) -> int:
        answer = -1
        for i, w in enumerate(self.words):
            if w[0:len(pref)] == pref and w[-len(suff):] == suff:
                answer = i
        return answer

풀이 

1. init: 단어 리스트 초기화
2. f: 단어리스트의 모든 단어를 순차적으로 탐색하며 주어진 접두사와 접미사를 가지는지 확인

2. 브루트포스2 => 시간초과

두 번째 시도도 브루트포스 이용한 풀이인데, 접두사와 접미사를 확인하는 함수를 변경해봤다.

1번 풀이와 달리 끝에서부터 단어를 탐색하여 조건을 충족하는 단어를 발견하면 바로 리턴할 수 있도록 수정했다. 그리고 접두사와 접미사를 확인하는 문자열 함수가 있다는 것을 발견해서 적용했다.

class WordFilter:

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

    def f(self, pref: str, suff: str) -> int:
        for i in range(len(self.words)-1, -1, -1):	# 끝 인덱스부터 탐색
            if self.words[i].startswith(pref) and self.words[i].endswith(suff):	# 문자열 함수 사용
                return i
        return -1

 

역시나 시간 초과이고..

끝에서부터 조사한다고 하더라도 조건을 충족하는 단어가 앞 순서에 배치되어있다면 마찬가지로 낮은 효율성을 가지는 것을 간과했다. 그리고 startswith나 endswiths는 C로 최적화되어  있어 실행 속도가 빠르고, 리스트 슬라이싱 비교 방식에 비해 추가 메모리 사용이 적어 더 효율적인 방식이 맞는 것 같다. 리스트 슬라이싱은 새로운 문자열을 생성하고, 생성할 때의 시간 복잡도에 더해 비교하는 시간이 추가로 필요하기 때문이다.

---

다른 풀이

해시 이용 풀이

f 함수를 건드릴 생각만 했지 초기화 함수를 건드릴 생각은 전혀 못했다. 이렇게 접근해도 되는 거였군.

class WordFilter:

    def __init__(self, words: List[str]):
        self.prefix_suffix_map = {}
        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.prefix_suffix_map[(prefix, suffix)] = index

    def f(self, pref: str, suff: str) -> int:
        return self.prefix_suffix_map.get((pref, suff), -1)

풀이

1. init: 단어 리스트에서 나올 수 있는 접두사 접미사 조합을 사전으로 만든다.
   key: (접두사, 접미사) , value: 접두사와 접미사를 포함하는 단어의 인덱스
   for문을 통해 순차 탐색하므로, 동일한 접두사와 접미사를 포함하는 단어 중 가장 큰 인덱스가 value에 저장된다.
2. f: get 함수를 이용하여 주어진 접두사와 접미사를 key값으로 하는 value(인덱스)를 반환한다.
   이 때 default 값은 -1로 하여, key 값이 없는 경우 -1을 반환한다.

 

내 풀이들은 단어리스트에서 f 함수를 호출할 때마다 모든 단어에 대해 비교 로직을 수행해야하기 때문에 시간 복잡도가 O(n*m) (n:단어수, m:단어평균길이) 이다. 테스트케이스의 경우, 단어도 매우 많고, f 함수의 매개변수도 많이 주어져 있었기 때문에 엄청나게 성능 저하를 유발하는 코드였던 것..!

 

반면에 해시를 이용한 풀이의 경우 초기화 시 계산이 O(n*m^2)으로 더 걸리지만, 이는 한 번만 발생하기 때문에 무리가 되지 않는다. f 메소드를 호출했을 때는 해시를 사용하여 O(1) 시간 복잡도를 가지므로, 훨씬 빠르게 검색 결과를 반환할 수 있다.

 

테스트케이스에서는 초기화는 한번만 발생하고 f 호출(검색)을 많이 수행하기 때문에 해시를 이용한 풀이가 적절한 풀이이다.

---

회고

리트코드를 처음 풀어봤는데, 객체에서 여러 함수가 있고, 각 함수를 정의하는 코드를 작성하는 풀이가 새로웠다.

문제에서 요구하는 것은 검색시 빠른 결과를 도출해내는 것인데, init 함수를 활용하지 못하고, f 함수에만 풀이를 하려고 하여 계속 실패했다. 조금 더 열린 사고가 필요할 듯 ㅎ.ㅎ.ㅎ

 

주제가 완전 탐색이다 보니 완전 탐색 알고리즘 종류를 알아놓으면 좋을 것 같다.

잘 정리된 블로그가 있어서 링크 걸어두기,,

https://velog.io/@hyehyes/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89