99클럽 코테 스터디 5기 2일차 TIL + 프로그래머스 가사 검색(Trie)

오늘의 학습 키워드

오늘은 회사에 퇴근하고나서 문제를 보았는데 프로그래머스 Lv.4의 가사 검색 문제를 풀게 되었다. 

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

프로그래머스

 

- 공부한 내용 본인의 언어로 정리하기

from collections import defaultdict

def solution(words, queries):
    # 사전 생성: 길이에 따른 단어와 역순 단어 저장
    word_dict = defaultdict(list)
    reverse_word_dict = defaultdict(list)

    for word in words:
        word_dict[len(word)].append(word)
        reverse_word_dict[len(word)].append(word[::-1])

    # 사전 정렬: 이진 탐색을 위한 준비
    for key in word_dict:
        word_dict[key].sort()
        reverse_word_dict[key].sort()

    def count_by_range(word_list, left, right):
        """left와 right 사이의 단어 개수를 찾는 함수"""
        from bisect import bisect_left, bisect_right
        return bisect_right(word_list, right) - bisect_left(word_list, left)

    answer = []
    for query in queries:
        if query[0] == '?':  # 접두사에 ?가 포함된 경우 (뒤집어서 검색)
            rev_query = query[::-1]
            left = rev_query.replace('?', 'a')
            right = rev_query.replace('?', 'z')
            answer.append(count_by_range(reverse_word_dict[len(query)], left, right))
        else:  # 접미사에 ?가 포함된 경우
            left = query.replace('?', 'a')
            right = query.replace('?', 'z')
            answer.append(count_by_range(word_dict[len(query)], left, right))

    return answer

- 오늘의 회고

1. 어떤 문제가 있었고, 나는 어떤 시도를 했는지

 

이번엔 트라이 자료구조가 나왔다. 99클럽 챌린저 모드로 난이도를 설정하니 정말 심화 알고리즘 내용으로 문제가 출제된다.

사실 이번에도 알고리즘을 떠올리기만 했을뿐 구현을 어떻게 해야할지 막혀서 못 풀었다. 어제에 벨만 포드에 이어 두번쨰 수치이다. 

 

2. 어떻게 해결했는지

 

트라이 알고리즘 학습후 적용해서 다시 풀어보았습니다.

 

3. 무엇을 새롭게 알았는지

• 트라이(Trie)

 

• 트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.
• 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조라고 한다.
• 예를 들어 'Datastructure'라는 단어를 검색하기 위해서는 제일 먼저 'D'를 찾고, 다음에 'a', 't', ... 의 순서로 찾으면 된다. 이러한 개념을 적용한 것이 트라이(Trie)이다.