[종만북]8.동적 계획법-와일드카드

문제

출처 : https://www.algospot.com/judge/problem/read/WILDCARD

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

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

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

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

입력

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

출력

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

풀이(책 참고)

문자열을 비교하는데 있어서 * 문자를 고려하여 비교하는 부분이 상당히 까다로웠다. *에 대응하는 글자수에 제한이 없기 때문에, 이를 어떻게 처리할 지를 해결하지 못했다. 또한 동적 계획법을 위해 어떤 부분을 메모이제이션을 통해 활용해야 하는지를 캐치하지 못하여 스스로 풀이에 실패하였다.

먼저 문자의 일치여부를 조사하는 방법은, 각 문자열을 한 글자씩 비교하여 *을 만나거나 둘 중 한 문자열이 끝날 때 멈추도록 한다. 이 때, 종료하는 경우는 다음과 같다.

각 문자가 서로 일치하지 않는 경우
패턴이 끝에 도달한 경우
파일명이 끝에 도달한 경우
패턴의 해당 문자가 *인 경우

1번의 경우, 실패한 것으로 종료하고 2번의 경우 패턴에서 *이 없는 경우로 패턴과 파일명의 길이의 일치여부에 따라 대응 여부가 결정된다. 3번의 경우, 패턴이 남았지만 파일명이 끝에 도달한 경우로 남은 패턴이 *인 경우 대응 될 수 있기 때문에 이러한 부분을 감안해야 한다.

4번의 경우가 핵심인데 패턴에서 *에 도달한 경우, 몇 글자가 대응될 지 모르므로 파일명에서 해당 위치부터 남은 문자열의 길이까지를 순회하여 검사하여야 한다. 이를 위해 재귀적으로 해당 검사함수를 호출하여 * 이후 문자가 일치하였을 때 대응된다고 볼수 있다.

문제는 이렇게 *에 대응되는 문자를 검사하기 위해 재귀적으로 호출함에 따라 오랜 시간이 걸릴 수 있다는 점이다. *에 대응되는 모든 글자수 조합을 검사하므로, 수많은 경우를 하나하나 검사하기 때문에 비효율적으로 검사가 이루어진다. 따라서 중복되는 계산을 효율적으로 처리하기 위해, 메모이제이션을 적용하여 각각의 문자에 대한 대응 여부를 다음과 같이 저장하도록 한다.

// 0 : 아직 계산되지 않음, -1 : 대응되지 않음, 1 : 대응됨
	static int wildCard(int p, int f) {
		int ret = cache[p][f];
		if (ret != 0)
			return ret;
		while (p < wild.length() && f < filename.length()
				&& (wild.charAt(p) == '?' || wild.charAt(p) == filename.charAt(f))) {
			p++;
			f++;
		}

		if (p == wild.length())
			return ret = ((f == filename.length()) ? 1 : -1);
		if (wild.charAt(p) == '*')
			for (int skip = 0; skip + f <= filename.length(); skip++)
				if (wildCard(p + 1, f + skip) == 1)
					return ret = 1;
		return ret = 0;
	}

메모이제이션에 사용된 전역 2차원 배열 cache는 각 문자열에서 해당 인덱스부터의 부분 문자들이 대응되는 여부를 저장한 배열로, cache[p] [f] 의 경우 패턴의 p번째 인덱스부터의 부분 문자열과, 파일명의 f번 째 인덱스부터의 부분 문자열의 대응 여부를 저장한 것이다. 따라서, 문자열을 부분적으로 비교함에 있어서 이전에 비교하였던 결과를 저장하였다가 해당 부분문자열을 다시 비교할 때 이전에 계산한 답을 호출하여 중복 계산을 막도록 한다.

함수 wildCard는 cache를 통해 패턴의 p, 파일명의 f 인덱스부터의 문자열의 대응 여부를 반환하는 함수로 각각의 문자를 비교하였을 때, *을 만난 경우 재귀적으로 함수를 호출하는데, 각각의 부분 문자열의 대응 여부를 함수가 호출됨에 따라 cache에 저장하므로 기저사례에서 해당 위치의 문자열들이 앞서 계산되어 이미 저장되어 있는 경우 값을 바로 출력하도록 하여 중복계산을 막고 빠른 비교가 이루어지도록 구현한다.

이번 문제를 통해 동적 계획법으로 풀이를 설계하기 위해서는 먼저 문제를 반복적으로 풀 수 있도록 접근하고, 중복이 발생하는 경우를 정확히 파악하여 어떤 부분에 메모이제이션을 적용시켜 중복 계산을 막을 것인지를 잘 생각해야 한다는 것을 느꼈다.

Menu

문제

입력

출력

풀이(책 참고)