[프로그래머스] 코딩테스트 연습 - 가사 검색(Python)

코딩테스트 연습 - 가사 검색 [2020 KAKAO BLIND RECRUITMENT]

코딩테스트 연습 - 가사 검색

 

풀이

개인적으로 쉽지 않은 문제였다고 생각합니다. 저는 이 문제를 풀기 전까지 Trie의 개념을 모르고 있었거든요ㅎㅎ

그래서 Trie를 사용하지 않고 선형 방법으로 구현했었는데 효율성 1~3번을 뚫기가 쉽지 않아 결국 Trie를 사용했습니다.

Trie의 개념은 간단합니다. 하나의 string을 Tree형태로 저장해서 빠른 문자열 검색에 적합하도록 만들어진 자료구조입니다.

Trie를 사용한다고 해도 문제를 풀기 위해서 생각해야 할 점이 하나 더 있습니다.

바로 "?"의 위치에 따라 (1) 접미사의 경우 (2) 접두사의 경우 (3) 전체가 "?"인 경우로 나뉘게 되어 각각에 대해 다른 Trie를 사용하는 것이 좋습니다. 왜냐하면 접두사의 경우인 query에 대해 접미사로 만들어진 Trie에서 검색하기란 Trie를 모두 탐색해야 하는 번거로움이 생기니까요.

또한 "질문하기"에서 힌트를 얻은 하나가 있는데 Trie를 word의 길이별로 만들어 저장하면 메모리는 더욱 커지지만 빠른 속도로 탐색이 가능해서 해당 방법으로 여러 Trie를 만들어 사용했습니다.

 

Code

from collections import defaultdict
def search(head, query):    # query는 '?'가 suffix의 위치로만 입력
    curr = head
    result = 0
    for char in query:
        if char == '?':     # '?'를 만나면 뒤의 모든 경우가 가능
            return result
        else:
            if char not in curr[0]:     # 가능한 단어가 없는 경우
                return 0
            result = curr[0][char][1]
            curr = curr[0][char]
    return result

def solution(words, queries):
    answer = []
    prefix, suffix = defaultdict(), defaultdict()
    for word in words:              # Trie 생성
        wlen = len(word)
        if wlen not in prefix:      # key값이 없을 때 추가
            prefix[wlen], suffix[wlen] = [{}, 0], [{}, 0]
        for dictionary, string in [[prefix, word], [suffix, word[::-1]]]:
            curr = dictionary[wlen]
            curr[1] += 1
            for char in string:     # Trie 형태로 word 추가
                if char not in curr[0]:
                    curr[0][char] = [{}, 0]
                curr[0][char][1] += 1
                curr = curr[0][char]

    for query in queries:       # 검색
        qlen = len(query)
        if qlen not in prefix:  # 길이가 맞지 않는 경우
            answer.append(0)
        elif query[0]=='?' and query[-1]=='?':  # 전부 '?'
            answer.append(prefix[qlen][1])
        elif query[0]=='?':     # suffix
            answer.append(search(suffix[qlen], query[::-1]))
        elif query[-1]=='?':    # prefix
            answer.append(search(prefix[qlen], query))

    return answer

 

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.

가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.

 

가사 단어 제한사항

• words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
• 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
• 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
• 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.

검색 키워드 제한사항

• queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
• 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
• 검색 키워드는 중복될 수도 있습니다.
• 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
• 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
  • 예를 들어 "??odo", "fro??", "?????"는 가능한 키워드입니다.
  • 반면에 "frodo"('?'가 없음), "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

 

입출력 예

words	queries	result
["frodo", "front", "frost", "frozen", "frame", "kakao"]	["fro??", "????o", "fr???", "fro???", "pro?"]	[3, 2, 4, 1, 0]