[문제][알고스팟]WILDCARD

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • WILDCARD
  • 2000ms
  • 65536kb
  • 7861
  • 2334 (29%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 연습문제
  • 보기

문제

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

와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 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

3가지 형태의 풀이가 있다.

첫번째는 완전탐색(match). 동적계획법을 사용하지 않기 때문에 시간이 오래 걸린다.

두번째는 DP 적용버전 (dynamicMatch) 문제 풀이가 가능하다.

세번째는 DP 적용버전에 시간복잡도를 낮춘것. (dynamicMatch2)

 

풀이

1. W, s 를 파라미터로 갖는 cache 배열을 만든다. 그리고 함수 진입시점에 값의 유무를 확인하고 있으면 리턴 없으면 이후 로직을 수행한다.
2. 반복문(while)으로 패턴의 현재 문자와 파일명의 현재 문자가 매칭되는 경우 (?포함) w와 s를 늘려나간다. 만약 반복문을 빠져나간다면 패턴의 길이가 더 짧거나, 파일명의 길이가 더 짧거나, '*'을 만난 경우이다. 패턴의 길이가 더 짧지만 마지막에 '*'이 있는 경우도 이후 로직에서 처리가 가능하다.
3. 반복문이 끝난 후, 패턴의 인덱스가 끝에 도달했고, 파일명의 인덱스도 끝에 도달했으면 정상적으로 매칭된 상태이므로 cache에 저장하고 리턴한다.
4. 하지만 '*'로 끝난 경우 재귀 호출한다. 단 패턴 인덱스는 하나 늘리고, 파일명 인덱스는 반복문으로 늘려가면서 '*'이 포함하는 케이스를 하나씩 늘려가면서 모두 재귀호출한다.
5. 나머지는 매칭 실패로 간주한다.

 

회고

1. 파일명이 패턴과 매칭되는 경우를 제외하고는 전부 '*'로 끝나는 케이스만 처리해주면 된다는 점을 직관적으로 생각해낼 수 없었다. 그 외의 접근법은 혼자 풀려고 했을때와 유사했다.
2. DP를 적용할때 인수를 w,s 두가지로 주면 참조적 투명 함수가 되는 것인지 와닿지 않았다. 혹은 참조적 투명함수가 되더라도 반복 호출된다는게 이해가 가지 않았다. 하지만 가장 쉬운 케이스로 손수 따라가보면 같은 인수의 함수가 반복 호출됨을 알 수 있었다. 그리고 하나의 패턴에 하나의 파일명에 대해서 DP가 적용되기 때문에 참조적 투명성 또한 충족된다.

 

package apss;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Wildcard_Solution {
	
	public static String W, S;
	public static int N;
	public static int cache[][];
	public static String fileName[];
	public static List<String> result;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		System.setIn(new FileInputStream("C://eclipse-workspace/sample_input.txt"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine().trim());
		for(int testCase=1; testCase<=T; testCase++) {
			
			W = br.readLine().trim();
			N = Integer.parseInt(br.readLine().trim());
			
			result = new ArrayList<String>();
			
			fileName = new String[N];
			for(int i=0; i<N; i++) {
				fileName[i] = br.readLine().trim();
				S = fileName[i];
				
				cache = new int[101][101];
				for(int k=0; k<101; k++) {
					for(int j=0; j<101; j++) {
						cache[k][j] = -1;
					}
				}
				
				bw.flush();
				
				if(dynamicMatch(0,0) == 1) {
					result.add(fileName[i]);
				}
				
			}
			
			Collections.sort(result);
			
			for(int i=0; i<result.size(); i++) {
				bw.write(result.get(i) + "\n");
			}
			
		}
		bw.close();
		
		

	}
	
	// 와일드카드 패턴 w가 문자열 s에 대응되는지 여부를 반환한다.
	public static boolean match(String w, String s) {
		// w[pos]와 s[pos]를 맞춰나간다.
		int pos = 0;
		while(pos < s.length() && pos<w.length() && (w.charAt(pos) == '?' || w.charAt(pos) == s.charAt(pos))) {
			pos++;
		}
		
		// 더이상 대응할 수 없으면 왜 while문이 끝났는지 확인한다.
		// 2. 패턴 끝에 도달해서 끝난 경우: 문자열도 끝났어야 대응됨
		if(pos == w.length()) {
			return pos == s.length();
		}
		
		// 4. *를 만나서 끝난 경우: *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인한다.
		if(w.charAt(pos) == '*') {
			for(int skip=0; pos+skip<=s.length(); skip++) {
				if(match(w.substring(pos+1), s.substring(pos+skip))) {
					return true;
				}
			}
		}
		
		// 이 외의 경우에는 모두 대응되지 않는다.
		return false;
	}
	
	// O(n^3) : 패턴길이 n, 문자열길이 n, 재귀호출 n
	public static int dynamicMatch(int w, int s) {
		// -1은 아직 답이 계산되지 않았음을 의미한다.
		// 1은 해당 입력들이 서로 대응됨을 의미한다.
		// 0은 해당 입력들이 서로 대응되지 않음을 의미한다.
		int ret = cache[w][s];
		if(ret != -1) {
			return cache[w][s];
		}
		
		// W[w]와 S[s]를 맞춰나간다.
		while(w<W.length() && s<S.length() && (W.charAt(w) == '?' || W.charAt(w) == S.charAt(s))) {
			w++;
			s++;
		}
		
		// 더이상 대응할 수 없으면 왜 while문이 끝났는지 확인한다
		// 2. 패턴 끝에 도달해서 끝난 경우: 문자열도 끝났어야 참
		if(w == W.length()) {
			return cache[w][s] = (s == S.length() ? 1 : 0);
		}
		
		// 4. *를 만나서 끝난 경우: *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인한다.
		if(W.charAt(w) == '*') {
			for(int skip=0; skip+s <= S.length(); ++skip) {
				if(dynamicMatch(w+1, s+skip) == 1) {
					return cache[w][s] = 1;
				}
			}
		}
		
		// 3. 이 외의 경우에는 모두 대응되지 않는다.
		return cache[w][s] = 0;
		
	}
	
	public static int dynamicMatch2(int w, int s) {
		// -1은 아직 답이 계산되지 않았음을 의미한다.
		// 1은 해당 입력들이 서로 대응됨을 의미한다.
		// 0은 해당 입력들이 서로 대응되지 않음을 의미한다.
		int ret = cache[w][s];
		if(ret != -1) {
			return cache[w][s];
		}
		
		// W[w]와 S[s]를 맞춰나간다.
		while(w<W.length() && s<S.length() && (W.charAt(w) == '?' || W.charAt(w) == S.charAt(s))) {
			return cache[w][s] = dynamicMatch2(w+1,s+1);
		}
		
		// 더이상 대응할 수 없으면 왜 while문이 끝났는지 확인한다
		// 2. 패턴 끝에 도달해서 끝난 경우: 문자열도 끝났어야 참
		if(w == W.length()) {
			return cache[w][s] = (s == S.length() ? 1 : 0);
		}
		
		// 4. *를 만나서 끝난 경우: *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인한다.
		if(W.charAt(w) == '*') {
			if(dynamicMatch2(w+1,s) == 1 || (s < S.length() && dynamicMatch2(w, s+1) == 1)) {
				return cache[w][s] = 1;
			}
		}
		
		// 3. 이 외의 경우에는 모두 대응되지 않는다.
		return cache[w][s] = 0;
		
	}

}