8.2_와일드 카드_WILDCARD

문제 설명

algospot.com :: WILDCARD

• 와일드카드 문자열 W가 주어진다.
• N개의 파일명이 주어진다.
• 파일명은 알파벳 대소문자, 숫자로 이루어져 있으며, 와일드카드는 * 와 ? 도 가질 수 있다.
• ? 는 해당 자리에 어떤 문자가 와도 된다.
• *는 해당 자리에 0글자 이상의 어떤 문자들이 와도 된다.

=> 와일드 카드에 매치되는 파일명들을 아스키 코드 순서대로 출력하기

 

 

문제 풀이

재귀함수를 이용해 와일드 카드와 각 파일명을 한글자씩 비교하는데,

와일드카드의 각 글자가 무엇인지에 따라 3가지 경우로 나눌 수 있다.

1. 알파벳이나 숫자일 경우(기호가 아닌 문자일 경우)
2. ? 일 경우
3. * 일 경우

1번의 경우와 2번의 경우는 각 글자를 1:1로 비교하면 된다.

 

하지만 3번, *일 경우가 문제인데, *의 자리에는 0글자 이상의 어떤 문자가 와도 되므로

1. 자리에 아무것도 없을 경우
2. *자리에 문자가 더 있을 경우
3. *자리에 문자가 더이상 없을 경우

이러한 3가지 경우로 또 나뉘어진다.

 

이 때, *일 경우에 나뉘는 3가지 경우는 연산 중복이 발생할 수 있기 때문에

메모이제이션을 이용하여 각 인덱스를 비교했을때의 결과를 저장하여 재사용한다.

 

 

문제 풀이 코드

#include <iostream>
#include <string.h>

#define MAXSIZE 100;

using namespace std;

int N;
char W[101];
char Cards[50][101];
char SortedCardIndexes[50][101];
char Answers[50][101];
int ansCnt;
int memoization[101][101];

int checkString(int order, int wIndex ,int cardIndex) {
	if (memoization[wIndex][cardIndex] != -1) return memoization[wIndex][cardIndex];

	int result = 0;

	// 둘 다 끝에 도달했을 경우이거나, 와일드카드의 끝이 *일 경우
	if ((W[wIndex] == '\0' && Cards[order][cardIndex] == '\0') || (W[wIndex] == '*' && W[wIndex + 1] == '\0'))
		result =  1;
	else if (W[wIndex] == '\0' || Cards[order][cardIndex] == '\0')
		result =  0;
	else if (W[wIndex] == '*')
		// * 자리에 아무것도 없을 경우 + * 자리에 문자가 더 있을 경우 + * 자리에 글자가 더이상 없을 경우
		result = checkString(order, wIndex + 1, cardIndex) + checkString(order, wIndex, cardIndex + 1) + checkString(order, wIndex + 1, cardIndex + 1);
	else if (W[wIndex] == '?')
		result = checkString(order, wIndex + 1, cardIndex + 1);
	else if (W[wIndex] == Cards[order][cardIndex])
		result = checkString(order, wIndex + 1, cardIndex + 1);
	
	memoization[wIndex][cardIndex] = result;
	return result;
}

int compare(char* str1, char* str2) {
	int index = 0;
	while (index <= 100) {
		if (str1[index] == str2[index])
			++index;
		else
			return str1[index] - str2[index];
	}
}

void merge(int left, int mid, int right) {
	int i = left;
	int j = mid + 1;
	int k = left;

	while (i <= mid && j <= right) {
		if (compare(Answers[i], Answers[j]) < 0) {
			memcpy(&SortedCardIndexes[k++], &Answers[i++], 101);
		}
		else {
			memcpy(&SortedCardIndexes[k++], &Answers[j++], 101);
		}
	}

	while (i <= mid) {
		memcpy(&SortedCardIndexes[k++], &Answers[i++], 101);
	}

	while (j <= right) {
		memcpy(&SortedCardIndexes[k++], &Answers[j++], 101);
	}

	for (int l = left; l <= right; ++l) {
		memcpy(&Answers[l], &SortedCardIndexes[l], 101);
	}
}

void merge_sort(int left, int right) {	// 머지 소트(합 정렬)
	int mid;

	if (left < right) {
		mid = (left + right) / 2;
		merge_sort(left, mid);
		merge_sort(mid + 1, right);
		merge(left, mid, right);
	}
}

int main() {
	int C;
	cin >> C;
	for (int tc = 1; tc <= C; ++tc) {
		memset(W, '\0', 101);
		memset(Cards, '\0', 50 * 101);
		memset(Answers, '\0', 50 * 101);
		ansCnt = 0;
		cin >> W;
		cin >> N;
		for (int i = 0; i < N; ++i) {
			cin >> Cards[i];
		}

		for (int i = 0; i < N; ++i) {
			memset(memoization, -1, 101 * 101 * sizeof(int));	// 메모이제이션 초기화
			bool result = checkString(i, 0, 0);					// 문자열 비교
			if (result > 0)
				memcpy(Answers[ansCnt++], Cards[i], 101);		// 답이면 정답 배열에 copy
		}

		merge_sort(0, ansCnt - 1);	// 아스키 코드 순으로 정렬

		for (int i = 0; i < ansCnt; ++i) {
			cout << Answers[i] << endl;
		}
	}
	return 0;
}