문제 링크: https://programmers.co.kr/learn/courses/30/lessons/60060?language=cpp
가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.
words
의 길이 (가사 개수)와 queries
의 길이(검색 키워드 개수)는 2 이상 100,000 이하.words
에는 중복되는 가사(단어)가 없다.?
와일드카드 문자로 이뤄져있음.Q. 와일드카드 문자가 접미사에 있다면?
A. 일반적인 방법대로 문자열을 앞에서부터 비교해야 한다.
Q. 와일드카드 문자가 접두사에 있다면?
A. 문자를 뒤에서부터 비교해야 한다. → 비용이 너무 많이 든다.
∴ words
내 모든 가사를 정방향과 역방향으로 나눠서 저장한다
beauty
= 6글자 → hashTable[6].push_back("beauty")
sort()
연산은 필수다. lower_bound(), upper_bound()
두 함수를 이용하고,upper_bound() - lower_bound()
가 검색 키워드 검색 결과(찾은 개수)가 된다.#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// words 내 원소 길이 별 해시 테이블 (arr: 정방향, reverseArr: 역방향)
vector<string> arr[10001], reverseArr[10001];
// origin 문자열에서 `from` 문자를 `to`로 치환한다.
string userReplace(string origin, string from, string to) {
int pos = origin.find(from, 0); // from 문자가 발견되는 첫 번째 위치 반환.
while (pos < origin.length()) { // origin 문자열 끝까지 순회하면서 변경.
origin.replace(pos, from.size(), to);
pos += to.size();
}
return origin;
}
// `vec`에서 찾으려는 문자열의 개수를 반환한다.
int getCount(const vector<string>& vec, string left, string right) {
auto rightIdx = upper_bound(begin(vec), end(vec), right);
auto leftIdx = lower_bound(begin(vec), end(vec), left);
// (e.g. fr??? -> fraaa ~ frzzz 영역 내에 있는 문자열 개수 반환.)
return rightIdx - leftIdx;
}
vector<int> solution(vector<string> words, vector<string> queries) {
// [과정 1]:: 모든 가사를 길이 별로 해시테이블에 저장한다.
for (auto& itr : words) {
arr[itr.length()].push_back(itr); // 정방향 해시테이블에 저장.
reverse(begin(itr), end(itr));
reverseArr[itr.length()].push_back(itr);// 역방향 해시테이블에 저장.
}
// [과정 2]:: 해시테이블 내 모든 요소를 알파벳 순으로 정렬한다.
for (auto& itr : arr) sort(begin(itr), end(itr));
for (auto& itr : reverseArr) sort(begin(itr), end(itr));
// [과정 3]:: 쿼리문의 '?'가 접두부에 있는지 접미부에 있는지 판단 후 계산한다.
vector<int> answer;
for (auto& itr : queries) {
int res = 0;
if (itr[0] == '?') {
reverse(begin(itr), end(itr));
res = getCount(reverseArr[itr.length()], userReplace(itr, "?", "a"), userReplace(itr, "?", "z"));
} else
res = getCount(arr[itr.length()], userReplace(itr, "?", "a"), userReplace(itr, "?", "z"));
answer.push_back(res);
}
return answer;
}