와일드 카드
문제
와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다.
이때 사용하는 문자열을 와일드카드 패턴이라고 한다.
와일드카드 패턴을 앞에서 한 글자씩 파일명과 비교해서 모든 글자가 일치했을 때 해당 와일드카드 패턴이 파일명과 대응된다고 말한다.
단 와일드카드 패턴에 포함된 ?는 어떤 글자와도 대응된다고 가정하며, *은 0글자 이상의 어떤 문자열에도 대응된다고 가정한다.
예를들어 he?p는 파일명 help, heap에는 대응하지만 hello에는 대응되지 않는다
와일드카드 패턴과 함께 파일명의 집합이 주어질 때, 그중 패턴에 대응되는 파일명들을 찾아내는 프로그램을 작성하시오.
입력
입력의 첫 줄에는 테스트 케이스의 수 C(1~10)
각 테스트 케이스의 첫 줄에는 와일드카드 패턴 W가 주어짐
그 다음줄에는 파일명의 수 n(1~50)이 주어지고, 그 후 n줄에 하나씩 각 파일명이 주어짐
모든 문자열의 길이는 1~100이며 공백을 포함하지 않음
예제입력 및 출력
입력
3
he?p
3
help
heap
helpp
*p*
3
help
papa
hello
*bb*
1
babbbc
출력
heap
help
help
papa
babbbc
소스 코드
#include <iostream>
using namespace std;
int Case;
//cache[wild][file] - pattern 문자열의 wild번과 file이름 문자열의 file번이 일치하면 1 다르면 0
int cache[101][101];
class WildCard {
private:
string pattern; //와일드카드 패턴
string filename[50]; //파일이름 배열
int filenum; //파일 이름 갯수
public:
void Input() {
cin >> pattern; //와일드카드 패턴 입력
cin >> filenum; //파일 이름 갯수 입력
//파일이름 입력
for (int i = 0; i < filenum; i++) {
cin >> filename[i];
}
}
int FindFileName(int wild, int file, int number) {
int w = wild, f = file;
//기저 사례 - 이미 계산된 값이면 다시 계산하지 않고 반환
if (cache[w][f] != -1)
return cache[w][f];
//파일이름과 와일드카드 패턴을 순회하며 한글자씩 비교
for (w, f; w < pattern.size() && f < filename[number].size(); w++, f++) {
//비교대상이 같거나 물음표일경우 계속 비교
if ((pattern[w] == filename[number][f]) || pattern[w] == '?')
continue;
else //비교 글자가 다르거나 다돌아서 범위를 넘으면 탈출
break;
}
//와일드 카드 패턴을 다 돌아서 탈출했을때
if (w == pattern.size()) {
if (f == filename[number].size()) {
cache[wild][file] = 1;
//파일 이름도 다돌았다면 - 일치하는 이름 -> true반환
return cache[wild][file];
}
else {
cache[wild][file] = 0;
//파일 이름이 남아있다 - 일치하지 않는 이름 -> false반환
return cache[wild][file];
}
}
//*을 만나서 탈출했을때
if (pattern[w] == '*') {
//*이 파일이름과 0개일치,1개일치, .... , 마지막까지 일치하는 모든 경우를 순회하여 계산
for (int i = 0; i <= filename[number].size()-f; i++) {
//패턴의 다음idx와 *이 일치한것 다음의 파일 idx와 비교
if (FindFileName(w + 1, f + i, number) == true) {
//결과값이 일치하면 cache저장
cache[wild][file] = 1;
return cache[wild][file];
}
}
}
cache[wild][file] = 0;
return cache[wild][file];
}
//각 file이름별 결과 호출
void Output() {
for (int i = 0; i < filenum; i++) {
memset(cache, -1, sizeof(cache));
if (FindFileName(0, 0, i))
cout << filename[i] << endl;
}
}
};
WildCard* wildcard;
int main(void) {
cin >> Case; //케이스 입력
wildcard = new WildCard[Case]; //케이스별 객체 생성
//입력받기
for (int i = 0; i < Case; i++)
wildcard[i].Input();
for (int i = 0; i < Case; i++)
wildcard[i].Output();
}문제 풀이
1. cache사용
- 반복적으로 와일드카드 패턴과 파일이름을 비교해야 하므로 각각 알파벳의 비교결과를 저장
ex) cache[wild][file]
와일드카드의 wild번 문자와 파일이름의 file번 알파벳이 일치하면 1 다르면 0을 저장한다.
2. 기저사례 반환
- cache값이 이미 저장되어 있으면 함수를 다시 계산할 필요가 없으므로 바로 cache값을 반환해준다.
3. 함수 탈출조건
문자를 하나씩 비교하는 반복문을 탈출했을 때
- 와일드카드 패턴과 파일으름을 모두 순회하였으면 일치하므로 cache에 1 저장 후 반환
- 와일드카드 패턴은 모두 순회하였으나 파일이름은 다 순회하지 않았다면 문자가 모두 일치할 수 없으므로 cache에 0 저장 후 반환
- '*'을 만나 탈출하였다면 -> 점화식으로 이동
4. 점화식
'*'은 모든 문자를 나타낼 수 있다.
- 와일드 카드 패턴이 '*'로 순회를 탈출하였다면 '*'이 파일이름의 0개와 일치할때~남은 파일이름 모두와 일치할때의 재귀함수 호출
ex) FindFileName(wild+1, file + '*'과 일치하는 문자 개수, 비교하는 문자열 번호)
- 재귀함수가 끝까지 호출되어 반환된 결과가 true이면 문자열이 일치할 수 있다.