(출처) https://algospot.com/search/?q=wildcard
주어진 2개의 문자열을 비교해서 정해진 규칙에 따라 True, False를 구분해 내는 문제. 주어진 문자열의 개별문자는 ? 문자, * 문자, 그 외의 모든 문자 총 3가지로 분류될 수 있다. 이때 * 문자를 제외한 개별문자들은 1:1 단순 비교 1번만으로도 True, False를 판정 지을 수 있지만 * 의 경우는 다소 복잡하다. * 는 정해진 개수 없이 모든 문자와 대응될 수 있다는 규칙이 존재하기 때문에 총 몇 개의 문자와 대응되는 지가 정해지지 않는다. 따라서 해당 문제의 핵심은 결국 * 을 어떻게 처리해야 할 것인지로 귀결된다.
* 의 처리
만약 주어진 패턴에 * 개별문자가 전혀 존재하지 않는다면 해당 문제는 주어진 패턴과 비교문자열의 단순한 1:1 비교, 즉 O(N) 시간복잡도로 해결할 수 있게된다. (두 문자열의 길이를 N이라고 가정했을 때)
따라서 고민할 필요도 없이 완전탐색으로 쉽게 문제를 해결할 수 있다.
하지만 패턴에 * 문자가 포함되는 순간,
*가 아무 문자에도 대응하지 않는 경우부터 시작해서 1개만 대응하는경우, 2개만 대응하는경우, ･･･, 남은 모든 문자에 모두 대응하는 경우
까지 모든 경우를 하나하나 확인해주어야한다. 따라서 패턴 문자열의 길이를 M 이라고 하고 비교문자열의 길이를 N 이라고 했을 때, 만약 패턴의 문자열이 모두 * 로 구성되어 있다고 가정하면
패턴의 각 * 문자 M 개에 N 개의 문자를 남김 없이 나누어 주는 경우의 수 == n+m-1 C m-1 의 경우의 수를 모두 확인해주어야 한다는 것.
문제에서는 M과 N에 올 수 있는 최대 수가 100이라고 주어졌으니 완전탐색으로 해당 문제를 해결할려면 최대 199 C 99 = 45274257328051640582702088538742081937252294837706668420660 개의 경우의 수를 모두 탐색해야 한다. 따라서 해당 문제는 절대 완전탐색으로 풀 수 없음을 알 수 있다.
따라서 단순한 완전탐색으로 모든 경우를 생각하며 접근하기보다는, 해당 문제를 풀기 위해서 반드시 해야만 하는 계산이 무엇인지에 대해 집중해보기로 했다.
우선 패턴의 모든 문자를 * 라고 가정했을 때, 각 패턴문자 * 들이 비교문자열의 아무 문자에도 대응하지 않는 경우부터 남은 모든 문자에 대응하는 경우까지를 모두 1번씩 계산하여 확인해본다 하더라도, 각 * 패턴문자 100 개가 각 비교문자열의 문자 100 개에 대해 모두 1번씩 대응해보는 경우의 수 = 100 x 100 = 총 10,000 개의 계산이면 충분하다.
따라서 bool * 문자 [패턴] [비교문자열] 와 같은 캐쉬 배열을 만들어서 진행된 결과를 저장해놓음으로써 중복되는 계산을 피하고 해당 문제를 진행하게 된다면 총 1 만개의 부분문제만 확인하고 해당 문제를 해결할 수 있다.
ex) bool * 문자 [0][51] == 패턴의 0번째 *가 비교문자열의 총 51개의 문자에 대응하는 경우의 성공, 실패 여부를 저장
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include<cstring>
using namespace std;
int cache[101][101];
bool check;
void print_ret(vector<string> &ret) {
sort(ret.begin(),ret.end());
for (int i = 0; i < ret.size(); i++) {
cout << ret[i] << "\n";
}
}
int checking(queue<char>& file, queue<char>& pattern, int fi, int pi) {
//메모이제이션
if (cache[pi][fi] != -1) return cache[pi][fi];
//기저사례
if (file.empty() || pattern.empty()) {
if (file.empty() && pattern.empty()) return check = true;
if (pattern.empty()) return 0;
else if (pattern.front() == '*') {
pattern.pop();
pi++;
checking(file, pattern, fi, pi);
}
return 0;
}
if (pattern.front() == '?') {
pattern.pop();
file.pop();
checking(file, pattern, ++fi, ++pi);
}
else if (pattern.front() == '*') {
queue<char> temp_f = file;
queue<char> temp_p = pattern;
int file_size = temp_f.size();
for (int i = 0; i < file_size + 1; i++) {
for (int j = 0; j < i; j++) temp_f.pop();
temp_p.pop();
fi += i;
int &memo = cache[pi][fi];
memo = checking(temp_f, temp_p, fi, ++pi);
pi--;
fi -= i;
temp_f = file;
temp_p = pattern;
}
}
else{
if (pattern.front() != file.front()) return 0;
pattern.pop();
file.pop();
checking(file, pattern, ++fi, ++pi);
}
}
void wildcard(queue<char>* files, queue<char> &pattern, int n) {
vector<string> ret;
for (int i = 0; i < n; i++) {
memset(cache, -1, sizeof(cache));
queue<char> file = files[i];
queue<char> temp_pattern = pattern;
check = false;
checking(files[i], temp_pattern, 0, 0);
if (check) {
string temp;
while(!file.empty()) {
temp.push_back(file.front());
file.pop();
}
ret.push_back(temp);
}
}
print_ret(ret);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int testcase;
cin >> testcase;
while (testcase--) {
queue<char> files[50];
queue<char> pattern;
string pattern_str;
string file;
cin >> pattern_str;
for (auto iter = pattern_str.begin(); iter < pattern_str.end(); iter++) pattern.push(*iter);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> file;
for (auto iter = file.begin(); iter < file.end(); iter++) files[i].push(*iter);
}
wildcard(files, pattern, n);
}
return 0;
}
기억하고 싶은 점
해답을 보고 나니 책에서 첫 번째로 서술되어 있는, 재귀함수 안에서 반복문을 돌려 탐색을 하는 O(N^3) 방법과 완전 같은 방식으로 코드를 짰다는 걸 확인할 수 있었다. 나는 코드를 짜고 나서도 대충 부분문제가 N^2 개이니까 당연히 O(N^2)의 시간복잡도를 가질 줄 알았는데 반복문의 영향으로 N^3이 된다고 하니 쉽게 납득이 잘 안되더라. 책의 서술에는 부분문제가 N^2개 있고 함수에서 반복이 최대 N 번이 이루어져 총 N^3이 된다고 하는데, 애시당초 반복문이 돌아가는 것은 N^2의 부분문제의 형성을 위한 것인데 왜 그것을 별개의 횟수로 계산하여 N을 한 번 더 곱해주는 것인지가 의문이었다.
그래서 O(N^2)의 구현과 비교하면서 차근차근 생각을 한 번 해보았다.
어쨌든 두 구현 모두 문제를 해결하기 위해서는 총 100 x 100 = 10,000 개의 부분문제를 한 번씩은 반드시 계산해야 한다는 것은 같았다.
즉 일단 반복문은 생각하지 않기로 하더라도 두 구현 모두 N^2의 부분문제의 계산이 필요하다는 것은 고정되어 있는 사실이며, 이 말은 두 구현 모두 재귀함수(해답에서는 matchMemoized 함수) 가 총 N^2번 실행 될 것이라는 말과 동일하다.
이 때, 전자의 경우 하나의 부분문제에 N번의 반복문이 포함되어 있지만 후자의 구현에는 반복 없이 단순히 다음 부분문제의 재귀호출 로직만이 존재한다. 따라서 전자는 O(N^3)의 시간복잡도를 갖고 후자는 O(N^2)의 복잡도를 갖는다. 이런 식으로 생각하니 약간은 이해가 되더라. 그런데 답을 알고 나서 그 과정을 유추해 나가는 것이 아니라, 답을 알기 전에 내가 과연 이런 식의 논리과정을 제대로 떠올릴 수 있을까 하는 의구심이 들었다. 앞으로 재귀문제의 시간복잡도를 계산해야할 때는 우선 크게 총 몇 번의 재귀반복이 필요한 지를 먼저 계산하고나서, 그 다음으로 부분문제 코드의 구현을 보며, 부분문제 하나당 얼마만큼의 시간이 소요되는 지 계산하는 습관을 들여놔야 겠다는 것을 느꼈다.
또한 마지막으로 의문과는 별개로 책의 두 번째로 서술되어 있는 재귀로직이 훨씬 더 명료하고 깔끔한 코드라는 것은 부정할 수 없었다. 해당 코드는 함수의 재귀적인 움직임을 말 그대로 재귀로서 명료하게 구현한 느낌이었다. 사실 내가 짠 코드는 재귀함수라고 보기에는 부분문제의 형성이 분명하지 않았고 그로 인해 생기는 여러 가지 예외를 따로 처리해 줬어야만 했다. 나도 이런 식의 깔끔한 구현이 가능하게 될 때까지 계속 의식하며 머리에 담아놓아야겠다는 것을 느꼈다.
