[프로그래머스][KAKAO_BLIND][2020] 가사 검색

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

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

 

내가 작성한 코드

from collections import defaultdict

def matched(dic, q):
    if not len(dic):
        return 0
    for c in q:
        if c == '?':
            break
        if c not in dic:
            return 0
        dic = dic[c]
    if "num" in dic:
        return dic["num"]
    return 0

def solution(words, queries):
    answer = []
    front = defaultdict(dict)
    rear = defaultdict(dict)

    for word in words:
        n = len(word)
        crnt = front[n]
        for c in word:
            if c not in crnt:
                crnt[c] = defaultdict()
            if "num" not in crnt:
                crnt["num"] = 0
            crnt["num"] += 1
            crnt = crnt[c]

        if "num" not in crnt:
            crnt["num"] = 0
        crnt["num"] += 1

        crnt = rear[n]
        for c in word[::-1]:
            if c not in crnt:
                crnt[c] = defaultdict()
            if "num" not in crnt:
                crnt["num"] = 0
            crnt["num"] += 1
            crnt = crnt[c]

        if "num" not in crnt:
            crnt["num"] = 0
        crnt["num"] += 1

    for q in queries:
        n = len(q)
        if q[0] == '?':
            answer.append(matched(rear[n], q[::-1]))
        else:
            answer.append(matched(front[n], q))

    return answer

• 깔끔한 코드를 만들고 싶은데 너무 어렵다
• regex로 풀었더니 시간초과다
  
  • query의 '?'를 '.'로 바꾸고, 양 옆에 '^', '$'를 붙여줌
  • 효율성 테스트 3개에서 시간초과

 

다른 사람이 작성한 코드

# 파이썬
from collections import defaultdict
from bisect import bisect_left, bisect_right

def count_by_lange(lst, start, end):
    return bisect_right(lst, end) - bisect_left(lst, start)

def solution(words, queries):
    answer = []
    cands = defaultdict(list)
    reverse_cands = defaultdict(list)
    # 길이별 저장
    for word in words:
        cands[len(word)].append(word)
        reverse_cands[len(word)].append(word[::-1])
    # 정렬 O(NlogN)
    for cand in cands.values():
        cand.sort()
    for cand in reverse_cands.values():
        cand.sort()
    # 탐색 O(N * logM)
    for query in queries:
        if query[0] == '?': # 와일드카드 접두사 일 때
            lst = reverse_cands[len(query)]
            start, end = query[::-1].replace('?','a'), query[::-1].replace('?','z')
        else: # 와일드카드 접미사 일 때
            lst = cands[len(query)]
            start, end = query.replace('?','a'), query.replace('?','z')
        answer.append(count_by_lange(lst, start, end))

    return answer

• trie를 사용하는 법도, len으로 나누는 법도 생각해봤었는데, 둘 다 사용할 줄 몰랐다
• 나는 bisect는 쉽게 떠오르지 않을 거 같아서 그냥 손수 작성하는 게 나을듯

https://velog.io/@tjdud0123/%EA%B0%80%EC%82%AC-%EA%B2%80%EC%83%89-2020-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EA%B3%B5%EC%B1%84-python

가사 검색 - 2020 카카오 공채 (python)

 

기억해야할 것

• 문제를 나누어 접근할 것 (제발...)
  
  • trie만 사용하면 길이가 문제이므로, 처음부터 len으로 나눔
  • trie를 순차적으로 만들면 prefix만, 거꾸로 만들면 suffix만 확인하므로 둘 다 만듦