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

🤔문제 해결

1. Lv4... | 트라이 자료구조

2. 트라이 자료구조를 구성한다.( 쉽게 말하자면 dict안에 dict안에 dict안에 dict.... 구조 )

대략 위의 그림과 같은 형태로 구성하게 된다. 맨 앞의 숫자는 길이가 5인 단어,  6인 단어

다음 f로 시작하는 단어 4개, r로시작하는 단어 4개, o로 시작하는 단어3개, d로 시작하는 단어 1개... 가 있다는 의미

4. 찾는다...

만약 'fro??' 을 찾는다고 하자

 (1) 길이가 5 인 곳으로 들어간다

 (2) 거기서 f 로 들어간다. cnt에는 f로 시작하는 단어가 4개있다는 것을 저장한다.

 (3) r 로 들어간다. cnt에는 r로 시작하는 단어가 4개 있다는 것을 저장한다.

 (4) o 로 들어간다. cnt에는 o로 시작하는 단어가 3개 있다는 것을 저장한다.

 (5) ? 를 만나면 cnt 를 리턴.

 (6) fro 로 시작하면서 길이가 5인 단어는 마지막에 저장된 3개이다.

 

💨 !!Tip하지만 이렇게만 하면 효율성 3번에서 틀린다. 이유는 쿼리가 모두 '?'로 구성된 경우가 있기 때문!!!!

해결법: 단어의 길이는 최대 1만까지이다. 1만까지의 배열을 만들고, 각 단어의 길이마다 몇개인지 저장

쿼리가 모두 '?'로 구성된 단어가 나오면 찾지말고 리스트에 저장해둔 갯수를 꺼낸다.

 

😎 트라이 구조를 이용하지 않고 문자를 잘라서 하나하나 찾아줘도 효율성 3번빼고 다 찾을 수는 있다.

( len('asdf') 는 한번선언하고 그 값을 써주자. 계속 저렇게 불러오면 효율 안좋다.

만약 시간이 없고 트라이구조를 모른다면 부분점수라도 챙겨보자

 

 

💻소스 코드

from collections import defaultdict
from collections import deque


def insert(part_trie, word):
    copy_trie = part_trie
    q = deque(list(word))
    while q:
        char = q.popleft()
        if char not in copy_trie:
            copy_trie[char] = [0, {}]
        copy_trie[char][0] += 1
        copy_trie = copy_trie[char][1]


def find(trie, query):
    cnt = 0
    copy_trie = trie
    if len(copy_trie) == 0:
        return 0

    q = deque(list(query))

    while q:
        char = q.popleft()
        if char == "?":
            return cnt
        else:
            if char not in copy_trie:
                return 0
            cnt = copy_trie[char][0]
            copy_trie = copy_trie[char][1]

    return cnt


def solution(words, queries):
    answer = []
    # 트라이 자료구조 활용하기!
    trie = defaultdict(dict)
    reversed_trie = defaultdict(dict)

    # !!!쿼리가 모두 물음표인 경우 시간 초과가 발생하므로, 문자 길이에 따라 갯수 저장
    length_list = [0] * 10001

    # trie 만들기
    for word in words:
        length_word = len(word)
        length_list[length_word] += 1

        insert(trie[length_word], word)
        insert(reversed_trie[length_word], word[::-1])

    # 찾기
    for query in queries:
        length_query = len(query)

        if query.count('?') == length_query:  # 쿼리가 모두 물음표인 경우
            answer.append(length_list[length_query])
            continue
        if query[0] == "?":  # 물음표로 시작하는 쿼리
            answer.append(find(reversed_trie[length_query], query[::-1]))
        else:
            answer.append(find(trie[length_query], query))

    return answer


qqq = [
    [["frodo", "front", "frost", "frozen", "frame", "kakao"], ["fro??", "????o", "fr???", "fro???", "pro?"]]
]
for q1, q2 in qqq:
    print(solution(q1, q2))

 

📕문제 확인

출처: 프로그래머스

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

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

 

---

문제 설명

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

친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "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??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

입출력 예

wordsqueriesresult

["frodo", "front", "frost", "frozen", "frame", "kakao"]

["fro??", "????o", "fr???", "fro???", "pro?"]

[3, 2, 4, 1, 0]

입출력 예에 대한 설명

• "fro??"는 "frodo", "front", "frost"에 매치되므로 3입니다.
• "????o"는 "frodo", "kakao"에 매치되므로 2입니다.
• "fr???"는 "frodo", "front", "frost", "frame"에 매치되므로 4입니다.
• "fro???"는 "frozen"에 매치되므로 1입니다.
• "pro?"는 매치되는 가사 단어가 없으므로 0 입니다.