[이코테] CH07 이진 탐색 실전문제 30번 가사 검색(답안X)

https://school.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 입니다.

 

거의 한시간 넘게 박아서 풀어서 너무 기뻤다

그러나 ........

ㅋㅋ 그럼 그렇지

효율성 1,2,3에서 바로 Cut(테스트케이스는 다 맞는데 시간복잡도에서 컷당했습니다)

음.... 뭐 어떻게 해야하지?

사실 내가 배운 선에선 다 한 것 같았다

이건 일단 내가 처음에 짰던 코드

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
def findStartIndex(queries,start,end,index):
    while start <= end:
        mid = (start + end) // 2
        if queries[index][mid] == '?' and (mid == 0 or queries[index][mid-1]!='?'):
            return mid
        elif queries[index][mid]!= '?':
         start = mid + 1  
        if queries[index][mid] == '?':
            end = mid - 1
    return 0
def findEndIndex(queries,start,end,index):
    
    while start <= end:
        mid = (start + end) // 2
        if queries[index][mid] == '?' and (mid == len(queries[index])-1 or queries[index][mid+1]!='?'):
            return mid
        if queries[index][mid]!= '?':
            end = mid - 1  
        if queries[index][mid] == '?':
            start = mid + 1
    return len(queries[index])-1
def solution(words, queries):
    answer = []
    for i in range(len(queries)):
        count = 0
        if queries[i][0] == '?' and queries[i][-1]!='?':
         start = 0
         end = findEndIndex(queries,0,len(queries[i])-1,i)
        elif queries[i][-1] =='?' and queries[i][0]!='?':
         end = len(queries[i]) - 1
         start = findStartIndex(queries,0,len(queries[i])-1,i)
        if queries[i][0] == '?' and queries[i][-1] == '?':
           end = len(queries[i]) - 1
           start = 0
           
        for j in range(len(words)):
         if start == 0 and end!=len(queries[i])-1: # ????x
            if queries[i][end+1:len(queries[i])] == words[j][end+1:len(queries[i])] and len(queries[i]) == len(words[j]):
                count +=1
         elif start!=0 and end == len(queries[i])-1: # o????
            if queries[i][0:start] == words[j][0:start] and len(queries[i]) == len(words[j]):
                count +=1
         elif start == 0 and end == len(queries[i])-1:
            if len(queries[i]) == len(words[j]):
                count +=1
        answer.append(count)
        
    return answer

보는사람은 굉장히 복잡할 수 있겠지만...

전 대학교에서 2년간 씨언어에게 괴롭힘당했던 사람이라

코드를 간결하게 쓰려고 해도 잘 안되는 것 같아요

최대한 안좋은 버릇 들기 전에.. 쓸 라이브러리들은 정리하고 가야지 싶네요

 

전 사실 IT기업 지원 생각도 없고.. 이거 보니까 LV4더라고요

나중에 2회독할때 한번 더 생각해보고

안되면 구글링으로 해결할게요..

구글링 대강 해보니 Trie 자료구조를 쓰거나 아예 새로운 방식으로 코드를 짜야 해서

55점짜리 코드라도 기록하고 갑니다..