[카카오 기출문제] '가사 검색' 문제 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1 의 풀이]

---

 

문제 설명

 

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

 

친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.

그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "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]

 

 

알고리즘 분석

 

• 나의 풀이 ( 시간 초과 )

import re

def solution(words, queries):
    answer = []
    queries = list(map(lambda x: x.replace('?', '.'), queries))

    print(words)
    for querie in queries:
        cnt = 0
        q = re.compile(querie)
        for word in words:
            if q.match(word) and len(word) == len(querie):
                cnt += 1
        answer.append(cnt)
    return answer

 

 처음에는 이런게 Level 4가 맞는지 의문이 들었으나 역시 카카오는 카카오였습니다. 

어중간한 코드로는 이 문제의 효율성 테스트를 통과할 수 없습니다. 

 

Trie 구조 같이 특수한 알고리즘을 사용해야지만 이 문제의 효율성 테스트를 통과할 수 있다고 합니다.  

 

 

 

• 다른 사람의 풀이 

from collections import defaultdict

class Node:
    def __init__(self, data):
        self.data = data  # 현재 노드를 상징하는 값
        self.count = 0  # 현재 노드가 소유한 모든 자식 노드의 숫자
        self.child = {} # 현재 노드의 자식 노드


class Trie:
    def __init__(self):
        self.head = Node(None)  # 최상위 노드를 생성

    def insert(self, string):
        cur = self.head  # 최상위 노드를 불러옴
        cur.count += 1  # cur.count를 1 올려줌

        for c in string:  # 입력받은 단어를 한 글자씩 c에 넣고 반복
            if c not in cur.child: # c가 cur.child에 없다면
                cur.child[c] = Node(c) # child[c]에 자식노드(c)를 생성
            cur = cur.child[c]  # cur.child[c]가 cur을 대체
            cur.count += 1  # cur을 대체하게된 cur.child[c]의 count를 + 1

    def count(self, prefix):
        cur = self.head  # 최상위 노드를 불러옴

        for c in prefix:  # 입력받은 단어를 한 글자씩 c에 넣고 반복
            if c not in cur.child: # c가 cur.child에 없으면
                return 0  # 0을 반환
            cur = cur.child[c]  # 있다면 자식노드로 이동

        return cur.count  # 최종적으로 자식노드에 도착했다면 cur.count를 반환


def solution(words, queries):
    answer = []

    tries = create_trie(words)  # Trie를 생성
    reversed_tries = create_trie(words, True)  # Trie를 거꾸로 생성

    for query in queries:
        answer.append(count_matched_word(tries, reversed_tries, query))

    return answer


def create_trie(words, is_reversed=False):
    trie_dic = defaultdict(Trie)  # dict를 생성할 시 기본적으로 Trie로 생성

    for word in words:
        if is_reversed:  # True일 경우, word를 뒤집는다.
            word = word[::-1]
        trie_dic[len(word)].insert(word) # trie_dict[word의 길이]에 word를 insert한다

    return trie_dic


def count_matched_word(tries, reversed_tries, query):
    no_mark_query = query.replace('?', '')  # 문자열 query 중에 모든 '?'를 ''로 바꿔줌

    if query[0] == '?':  # 첫 문자가 ?일 경우
        return reversed_tries[len(query)].count(no_mark_query[::-1])
    else:  # tries[query의 길이].count()
        return tries[len(query)].count(no_mark_query)

 

 

참고할 만한 블로그 

 

•  Trie 구조에 대해서 그림으로 잘 설명해놓은 블로그 

프로그래머스 - 가사검색- Trie자료구조

 

• 코드의 원본이 있는 블로그 

[프로그래머스] 가사 검색 / 2020 KAKAO BLIND RECRUITMENT / python

 

 

 

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