20년도 카카오 블라인드 - 가사 검색

코딩테스트 연습 - 가사 검색 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

가사 검색

문제 설명

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

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

---

[문제 해설]

 

이 문제는 frodo 라는 단어가 주어졌을 때 "fro??", "????o", "fr???", "fro???", "pro?" 리스트에서 매칭 될 가능성이 있는 문자열의 개수를 찾는 문제입니다.

 

간단하게 일일히 찾아서 풀고자 한다면 frodo 단어 탐색 n, fro?? 단어 탐색 n, 리스트 순회 n

고로 o(n^3)이 걸릴 거로 예상된다.

이문제는 효율성 테스트가 있으므로 당연히 틀린다.

 

그럼 어떻게 풀어야 할까?

본인은 이진탐색으로 문제를 풀고자 한다.

원리는 이렇다

 

1. fro?? 라는 문자열이 주어졌을 때 이러한 문자열들 전체를 문자열 길이를 인덱스로 하여 각각 리스트에 넣어 버린다.

2. 각각의 리스트를 정렬 해주면, 

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

요렇게 될거다.

3. 그럼 각각의 리스트들을 정렬해줄 거다 => 그럼 각각의 크기별로 정렬될 것입니다.

4. 그러면 우리는 fro?? 가 주어졌을 때? 대신에 각 a, z 넣어서 froaa ~ frozz에 있는 이진 탐색하는 방식으로 찾을 겁니다.

다시 말하면 ['frame', 'frodo', 'front', 'frost', 'kakao'] 문자열들 중에서 froaa ~ frozz 사이에 있는 개수를 구하고자 한다는 겁니다.

여러 문제를 풀 때 혹시 1 1 2 2 2 2 3 3 3이라는 정렬된 리스트가 주어질 때 2의 개수를 구하는 문제를 구한 적이 있나요? 이렇게 이진 탐색으로 문제를 풀지 않았나요? 마찬가지의 원리입니다. (조금 생각해보시길...)

5. 그러면 이제 queries가 다 소진될 때까지의 위의 알고리즘 대로 문제를 풀면 됩니다.

 

저는 이진 탐색 메서드를 이용해서 풀었습니다.

 

from bisect import bisect_left, bisect_right


def countByRange(a, leftVal, rightVal):
    rightIdx = bisect_right(a, rightVal)
    leftIdx = bisect_left(a, leftVal)

    return rightIdx - leftIdx

딱 보면 아시겠지만 bisect_right는 a라는 배열에서 rightval을 만족하는 값들 중 가장 오른쪽 인덱스를 반환하고, 다음 줄은 left를 반환하는 코드이고, 결론적으로 원하는 val의 구간의 길이를 구할 수 있습니다.

 

---

[시간 초과된 코드]

 

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

    for querie in queries:
        ans = 0
        for word in words:
            isAns = True
            for i in range(len(word)):
                if len(word) != len(querie):
                    isAns = False
                    break

                if querie[i] == '?':
                    continue

                if querie[i] != word[i]:
                    isAns = False
                    break

            if isAns:
                ans += 1

        answer.append(ans)

    return answer

 

[맞은 코드]

 

from bisect import bisect_left, bisect_right


def countByRange(a, leftVal, rightVal):
    rightIdx = bisect_right(a, rightVal)
    leftIdx = bisect_left(a, leftVal)

    return rightIdx - leftIdx


array = [[] for _ in range(10001)]
reArray = [[] for _ in range(10001)]


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

    # 0. 뒤집힌 문자열으 고려하는 이유는 현재 원리가 "fro" 추정 가사를 찾는 거라면
    # 해당 여분의 공간에 fro??일때 frooaa ~ frozzz를 기입해서 탐색을 할 것이기 때문이다
    # 그런데 ?와일드 카드가 거꾸로 올 경우 그럴 수 없기 때문에
    # 뒤집어서 한 번 더 같은 원리를 적용하는 것
    # 1. 모든 단어를 길이 별로 삽입 ( 뒤집힌 문자도 고려 )
    for word in words:
        array[len(word)].append(word)
        reArray[len(word)].append(word[::-1])

    # 2. 제한개수 10000의 길이마다 정렬 수행
    for i in range(10001):
        array[i].sort()
        reArray[i].sort()

    # 3. queries를 돌면서 ?가 앞, 뒤에 따라 countByRange 실행
    for q in queries:
        if q[0] != '?':
            res = countByRange(array[len(q)], q.replace('?', 'a'), q.replace('?', 'z'))
        else:
            res = countByRange(reArray[len(q)], q[::-1].replace('?', 'a'), q[::-1].replace('?', 'z'))

        answer.append(res)

    return answer

 

---

후기

 

이전에 풀었던 문제인데 또 틀려서 이제까지 풀었는데 포스팅하지 않아서

쌓인 문제가 많음에도 이문제를 바로 포스팅했습니다.

다음에는 꼭 한 번에 풀어버리길...