[프로그래머스/C++] 가사 검색

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

1. 문제

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

가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.

2. 제한사항

• words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
• 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
• 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
• 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.

3. 검색 키워드 제한사항

• queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
• 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
• 검색 키워드는 중복될 수도 있습니다.
• 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
• 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
  • 예를 들어 "??odo", "fro??", "?????"는 가능한 키워드입니다.
  • 반면에 "frodo"('?'가 없음), "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

4. 풀이

• [C++] 정렬된 배열에서 특정 수의 구하기 이 문제를 기반으로 풀 수 있다.
  효율성 테스트가 있기 때문에 단순하게 비교하는 식으로 구현하면 시간 초과가발생한다.
• words 배열의 문자열 값들을 문자열의 길이에 따라 분류하여 vector<int> arr[문자열의 길이]에 저장한다.
• upper_bound와 lower_bound를 적용하기 위해 arr를 정렬한다.
• queries 배열의 문자열을 순서대로 뽑아 countByRange 함수를 호출하여 값을 받아와 answer 배열에 차례대로 저장한다.
• countByRange 함수의 leftValue 값으로 와일드 카드 문자 ?를 a로 변경한 값을 넘겨준다.
• countByRange 함수의 rightValue 값으로 와일드 카드 문자 ?를 z로 변경한 값을 넘겨준다.
  • ex) fro?? -> countByRange(arr, "froaa", "frozz")
  • fro??는 froaa부터 frozz 사이에 있는 문자열을 모두 포함하게 된다.
• 와일드 카드 문자열이 앞에 있는 경우는 위의 과정을 동일하게 처리하기 위애 모든 문자열을 뒤집어서 배열(reversed_arr)에 저장해둔다.
• reversed_arr에 위와 똑같은 과정을 통해 결과 값을 answer 배열에 저장한다.

countByRange 함수

int countByRange(vector<string> &v, string leftValue, string rightValue) {
    vector<string>::iterator rightIndex = upper_bound(v.begin(), v.end(), rightValue);
    vector<string>::iterator leftIndex = lower_bound(v.begin(), v.end(), leftValue);
    
    return rightIndex - leftIndex;
}

5. 처음 코드와 달라진 점

• 와일드 카드 위치에 따른 조건문을 반대로 처리해줘서 수정해주었다.

6. 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int countByRange(vector<string> &v, string leftValue, string rightValue) {
    vector<string>::iterator rightIndex = upper_bound(v.begin(), v.end(), rightValue);
    vector<string>::iterator leftIndex = lower_bound(v.begin(), v.end(), leftValue);
       
    return rightIndex - leftIndex;
}

string replaceAll(string s, char from, char to) {
    for(int i = 0; i < s.size(); ++i) {
        s[i] = s[i] == from ? to : s[i];
    }
    return s;
}

vector<string> arr[100001];
vector<string> reversed_arr[100001];

vector<int> solution(vector<string> words, vector<string> queries) {

    vector<int> answer;
    for(string word : words) {
        arr[word.size()].push_back(word);
        reverse(word.begin(), word.end());
        reversed_arr[word.size()].push_back(word);
    }
    
    for(int i = 0; i<100001; ++i) {
        sort(arr[i].begin(), arr[i].end());
        sort(reversed_arr[i].begin(), reversed_arr[i].end());
    }
    
    for(string query : queries) {
        if(query[0] != '?') {
            answer.push_back(countByRange(arr[query.size()], replaceAll(query, '?', 'a'), replaceAll(query, '?', 'z')));
        }
        else {
            reverse(query.begin(), query.end());
            answer.push_back(countByRange(reversed_arr[query.size()], replaceAll(query, '?', 'a'), replaceAll(query, '?', 'z')));
        }
    }
    
    return answer;
}