문제 출처 : https://algospot.com/judge/problem/read/WILDCARD
algospot.com :: WILDCARD
Wildcard 문제 정보 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를
algospot.com
문제
와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만,*나?와 같은 특수 문자를 포함한다.
와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된?는 어떤 글자와 비교해도 일치한다고 가정하며,*는 0 글자 이상의 어떤 문자열에도 일치한다고 본다.
예를 들어 와일드 카드he?p는 파일명help에도,heap에도 매치되지만,helpp에는 매치되지 않는다. 와일드 카드*p*는 파일명help에도,papa에도 매치되지만,hello에는 매치되지 않는다.
와일드카드 문자열과 함께 파일명의 집합이 주어질 때, 그 중 매치되는 파일명들을 찾아내는 프로그램을 작성하시오.
입력
입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 10) 가 주어진다. 각 테스트 케이스의 첫 줄에는 와일드카드 문자열 W 가 주어지며, 그 다음 줄에는 파일명의 수 N (1 <= N <= 50) 이 주어진다. 그 후 N 줄에 하나씩 각 파일명이 주어진다. 파일명은 공백 없이 알파벳 대소문자와 숫자만으로 이루어져 있으며, 와일드카드는 그 외에 * 와 ? 를 가질 수 있다. 모든 문자열의 길이는 1 이상 100 이하이다.
출력
각 테스트 케이스마다 주어진 와일드카드에 매치되는 파일들의 이름을 한 줄에 하나씩 아스키 코드 순서(숫자, 대문자, 소문자 순)대로 출력한다.
풀이
기존에 dp 문제를 풀 땐 반복적 동적 계획법으로 구현 했는데, 알고리즘 문제 해결 전략 책에서는
보다 직관적인 재귀 호출을 통한 메모이제이션으로 구현하기 때문에,
책을 보면서 dp를 풀어보면 dp를 정복하는 데에, 재귀까지 좀 더 익숙해질 수 있다.
아래의 두 코드중 시간복잡도가 O(N^3)인 코드는 내부에서 첫 *를 찾고, *에 몇 글자가 대응되어야 할지
검사하는 반복문이 존재하기 때문이다.
재귀함수 내에서 이러한 반복문을 모두 없애서 O(N^2)로 만든 것이 밑에 있는 코드이다.
코드(O(N^3))
#include <iostream>
#include <string>
#include<cstring>
#include <vector>
#include <algorithm>
using namespace std;
string wild, file;
int cache[101][101];
bool matchMemoized(int w, int f) {
//ret가 cache[w][f]의 참조형이라 ret의 값을 바꾸면 cache[w][f]의 값도 변함
int &ret = cache[w][f];
if (ret != -1)
//이미 ret가 갱신된 경우
return ret;
while (w < wild.length() && f < file.length() && (wild[w] == '?' || wild[w] == file[f])) {
//더이상 대응할 수 없을 때까지 w,f 늘리기
w++;
f++;
}
//while문 끝나면 왜 while문이 끝났는지 확인
if (w == wild.size() && f == file.size()) {
//문자열도 끝나고 패턴도 끝난 경우
return ret = 1;
}
if (wild[w] == '*') {
//*를 만나서 끝난 경우 : *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인
for (int skip = 0; skip + f <= file.length(); skip++) {
if (matchMemoized(w + 1, f + skip)) {
return ret = 1;
}
}
}
return ret = 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t,n;
cin >> t;
while (t--) {
vector<string> vt;
cin >> wild;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> file;
memset(cache, -1, sizeof(cache));
if (matchMemoized(0, 0) == 1) {
vt.push_back(file);
}
}
sort(vt.begin(), vt.end());
for (int i = 0; i < vt.size(); i++) {
cout << vt[i] << '\n';
}
}
return 0;
}코드(O(N^2))
#include <iostream>
#include <string>
#include<cstring>
#include <vector>
#include <algorithm>
using namespace std;
string wild, file;
int cache[101][101];
bool matchMemoized(int w, int f) {
//ret가 cache[w][f]의 참조형이라 ret의 값을 바꾸면 cache[w][f]의 값도 변함
int &ret = cache[w][f];
if (ret != -1)
//이미 ret가 갱신된 경우
return ret;
if (w < wild.length() && f < file.length() && (wild[w] == file[f] || wild[w] == '?')) {
//더이상 대응할 수 없을 때까지 w,f 늘리면서 재귀 호출
return ret = matchMemoized(w + 1, f + 1);
}
if (w == wild.length() && f == file.length()) {
//문자열도 끝나고 패턴도 끝난 경우
return ret = 1;
}
if (wild[w] == '*') {
if (matchMemoized(w + 1, f) || (f < file.length() && matchMemoized(w, f + 1))) {
//0글자와 대응되는 경우, 한 글자, 두 글자, ~글자 더 대응되는 경우
return ret = 1;
}
}
return ret = 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t,n;
cin >> t;
while (t--) {
vector<string> vt;
cin >> wild;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> file;
memset(cache, -1, sizeof(cache));
if (matchMemoized(0, 0) == 1) {
vt.push_back(file);
}
}
sort(vt.begin(), vt.end());
for (int i = 0; i < vt.size(); i++) {
cout << vt[i] << '\n';
}
}
return 0;
}
댓글