BOJ - (Algospot) WILDCARD 해결 전략 (C++)

• 문제

  와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다.

  와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자열에도 일치한다고 본다.

  예를 들어 와일드 카드 he?p 는 파일명 help 에도, heap 에도 매치되지만, helpp 에는 매치되지 않는다. 와일드 카드 p 는 파일명 help 에도, papa 에도 매치되지만, hello 에는 매치되지 않는다.

  와일드카드 문자열과 함께 파일명의 집합이 주어질 때, 그 중 매치되는 파일명들을 찾아내는 프로그램을 작성하시오.

• 입력

  입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 10) 가 주어진다. 각 테스트 케이스의 첫 줄에는 와일드카드 문자열 W 가 주어지며, 그 다음 줄에는 파일명의 수 N (1 <= N <= 50) 이 주어진다. 그 후 N 줄에 하나씩 각 파일명이 주어진다. 파일명은 공백 없이 알파벳 대소문자와 숫자만으로 이루어져 있으며, 와일드카드는 그 외에 * 와 ? 를 가질 수 있다. 모든 문자열의 길이는 1 이상 100 이하이다.

• 출력

  각 테스트 케이스마다 주어진 와일드카드에 매치되는 파일들의 이름을 한 줄에 하나씩 아스키 코드 순서(숫자, 대문자, 소문자 순)대로 출력한다.

• 예제 입력
  2
  he?p
  3
  help
  heap
  helpp
  p
  3
  help
  papa
  hello

• 예제 출력
  heap
  help
  help
  papa

해결 전략

  여전히 최초 풀이 시도에서 성공하지 못하고 있다. 이번엔, 문제의 접근 방식 자체는 괜찮았는데, 코딩 기술적인 측면에서 찾기 힘든 메모리 위치적 문제가 발생해 끝내 해결하지 못하였다. string 배열 선언 및 사용과 관련된 문제 같은데 그 원인을 잘 모르겠다. 추측하건데, 아마 cstring 헤더 미선언 혹은 vector 미사용 등이 이유가 되지 않을까 싶은데, 이는 추후 알아봐야겠다.

  한편, 본 문제는 전형적인 Dynamic Programming 문제이다. 보다 엄밀히 말하면, 완전탐색으로 문제를 접근하되, 결과의 재사용을 추구하는 유형이다. 완벽히 DP적 특성을 보인다고 느껴지진 않는다. 완전 탐색을 보다 더 최적화시킨 형태라고 보는 것이 더 맞겠다. 물론 결국 크게 봤을땐 그게 곧 DP이긴 하지만.

  문제의 접근에서 가장 주요한 Idea는 당연 *의 처리에 있다. ?의 처리는, 문제 상황을 조금만 이해해보면, 굳이 할 필요가 없음을 알 수 있다. 한 글자만 대응된다는 특성 때문이다. 아스타리스크의 처리에 있어서 가장 주요한 생각은 다음과 같다.

' ㅁㅁ* '와 같이, 아스타리스크로 끝나는 조각으로 문자열을 나누어 보자.

또한, 입력된 파일명들에 대해 각각 개별적으로 solve를 시도한다. 이렇게 해야 DP의 적용이 편리하다.

  이때, cache를 어떻게 사용할까에 대한 의문이 생긴다. cache는 현재 조회하고 있는 파일명과, 기준이 되는 와일드카드 포함 문자열, 이 둘을 각각 filename, wildcard라고 둔 다음, 이 둘을 문자열의 처음부터 선형적으로 매칭 관계를 파악할 때, 체크하고 있는 문자열의 인덱스를 기록한다.

  즉, cache[w][f]라 함은, wildcard의 w위치까지와, filename의 f위치까지의 매칭 관계를 보는 것이다. -1이면 계속 매칭을 해가야하는 상황이다. 따라서 -1로 초기화한다. 1은 최종적으로 매칭되는 상황. 즉, 만족하는 상황이고, 0은 최종적으로 매칭되지 않는 상황을 의미한다. cache에 이 데이터들을 넣어 결과의 재사용을 도모하는 것이다.

  앞서 말한 것처럼, 아스타리스크로 끝나는 조각 단위로 나눈다고 했다. 아스타리스크를 만난 이후의 처리를 어떻게 해야하는 것일까? 이는 아래의 조건으로 해결할 수 있다.

(matchMemoized(w + 1, f) || (f < filename.size() && matchMemoized(w, f + 1)))

  ||를 기준으로 첫 번째 조건은, 아스타리스크 이후의 wildcard 내 문자를 본다. 즉, 다음 조각으로 넘어가는 상황이다. 두번째 조건을 만족시키지 못했을 때, 이 첫번째 조건이 작동한다고 보면 된다. 또는, 아스타리스크로 아예 wildcard가 끝나는 상황을 확인하기도 한다. 두 번째 조건의 경우, f의 남아있는 부분을 쭉 선형적으로 체크한다. 안맞는 순간이 되면, 첫번째 조건을 보는 것이다. 결국 첫번째와 두번째 조건에 의해 매칭이 되거나, 아예 비매칭이거나 둘 중 하나로 결말을 맞이할 것이다.

  여기까지가 주요한 전략이다. Detail한 내용은 주석으로 대체한다. 한편, 개인적인 소회로는, 아래의 정오 코드에서 나타나는 주요 기술들을 체화시켜, 앞으로 string을 다룰 때에 발견하기 어려운 메모리 관련 오류를 미연에 방지해야할 것이라 생각한다. 아래는 코드이다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
// Algospot - WILDCARD
using namespace std;

int cache[101][101]; // 문자열의 최대 길이가 100이므로 널문자를 포함하여 101

string wildcard, filename;

// Dynamic Programming
// -1 : 계속 탐색해야함을 의미
// 1 : 와일드카드가 올바르게 사용되었음을 의미 (매칭)
// 0 : 두 문자열이 매칭되지 않음을 의미

int matchMemoized(int w, int f) { // memoization
	int &result = cache[w][f];	// w와 f까지 이미 체크되었는지 확인한다.

	if (result != -1)	// 캐시에 저장된 결과에 따라서
		return result;	// -1일때, 즉, 계속 확인해야할 때만 아래로 내려감.

	// wildcard와 filename을 선형적으로 읽어나간다.
	if (w < wildcard.size() && f < filename.size() &&
		(wildcard[w] == '?' || wildcard[w] == filename[f]))
		return result = matchMemoized(w + 1, f + 1);
	// 문제 상황 상 ?는 아무 문자나 대응되면 되고, 두 인덱스의 문자가 같을때도 킵고잉

	// 더 이상 대응할 수 없으면 while문이 종료된 케이스를 확인한다.
	// 문자열의 끝에 도달해서 종료된 경우 : 길이만 같으면 된다. 위의 조건에 의해 
	if (w == wildcard.size() && f == filename.size())
		return result = 1;

	// *를 만나서 종료된 경우: *에 몇 글자가 대응하는지 재귀호출로 확인
	if (wildcard[w] == '*') {	// ㅁㅁ* 조각 이후의 조각 확인하는데,
		if (matchMemoized(w + 1, f) ||
			(f < filename.size() && matchMemoized(w, f + 1)))
			return result = 1;
		// *에 대응 문자 없는 경우, 또는 한 글자 더 대응하는 경우(또 다른 조각있는경우)
	}

	// 이 외의 경우는 모두 대응 x
	return result = 0;
}

int main(void) {
	int c;

	cin >> c;
	while (c--) {
		vector<string> v;	// 주목할만한 기술
		int n;

		cin >> wildcard;
		cin >> n;

		for (int j = 0; j < n; j++) {
			memset(cache, -1, sizeof(cache));	// 캐시를 모두 -1로

			cin >> filename;

			if (matchMemoized(0, 0) == 1) // 매칭된 경우에만 벡터에 삽입(정렬위함)
				v.push_back(filename);
		}

		sort(v.begin(), v.end()); // 출력 조건 충족

		for (int j = 0; j < v.size(); j++)
			cout << v[j] << '\n';

		cout << '\n';
	}

	return 0;
}