[Programmers] 가사 검색 (Lv.4) 2024/4/18

문제 제목	정답률	난이도
가사 검색	47%	Lv.4

프로그래머스

 

문제요약
노래에 있는 단어 집합 words(중복 X), 검색 키워드 집합 queries가 주어진다.
조건 1) words 2~100,000개, word 길이 1~10,000, 소문자로만 구성
조건 2) queries의 길이 2~100,000, query의 길이 1~10,000,? 하나 이상 포함(접두사나 접미사로만 가능)
 

풀이

Step1. 효율성 테스트 존재->search시 binary search(log n) 생각 (words*queries시 시간복잡도 초과)
Step2. 접두사와 접미사에 붙을 경우 차이

• 접미사에 붙을경우 *aa~*zz로 찾을 수 있을
• 접두사를 접미사로 변환하려면 reverse사용 -> [::-1]

 

코드

from collections import Counter
def search_right(words_list, word):
    start_idx=0
    end_idx=len(words_list)
    while start_idx<end_idx:
        mid=(start_idx+end_idx)//2
        if words_list[mid]==word:
            return idx
        elif words_list[mid]<word:
            start_idx=mid+1
        else:#>start
            end_idx=mid
    return start_idx
                
            
def solution(words, queries):
    # 1 이상 10,000 이하
    word_list=[[] for _ in range(10001)]#0~10,000
    word_list_reverse=[[] for _ in range(10001)]#0~10,000
    for word in words:
        word_list[len(word)].append(word)
        word_list_reverse[len(word)].append(word[::-1])
    for word, word_reverse in zip(word_list, word_list_reverse):
        word.sort()
        word_reverse.sort()
    
    answer=[]
    for query in queries:
        query_count=Counter(query.split('?'))
        question_len=query_count['']
        if query[0]=='?':
            query=query[::-1]
            start=query[:-question_len]+'a'*question_len
            end=query[:-question_len]+'z'*question_len
            start_idx=search_right(word_list_reverse[len(query)], start)
            end_idx=search_right(word_list_reverse[len(query)], end)
        else:#*?
            start=query[:-question_len]+'a'*question_len
            end=query[:len(query)-question_len]+'z'*question_len
            start_idx=search_right(word_list[len(query)], start)
            end_idx=search_right(word_list[len(query)], end)
        answer.append(end_idx-start_idx)
    return answer