와일드 카드 (난이도: 중)

1. 문제 설명

(1) 와일드 카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다.

 

(2) 이때 사용하는 문자열을 와일드 카드 패턴이라고 하는데, 패턴은 일반적인 파일명과 비슷하지만 특수 문자

* 또는 ?를 포함할 수 있는 문자열이다.

 

(3) 와일드 카드 패턴을 앞에서 한 글자씩 파일명과 비교해서 모든 글자가 일치했을 때 해당 와일드 카드 패턴이

파일명과 대응된다고 말한다.

 

(4) 와일드 카드 패턴을에 포함된 "?"는 어떤 글자와도 대응된다고 가정하며, "*"는 0 글자 이상의 어떤 문자열에도 

대응된가고 가정한다.

 

( 예시1) 와일드 카드 he?p는 파일명 help와 heap에 대응되지만, helpp에 대응되지 않습니다. )

( 예시2) 와일드 카드 *p*는 파일명 help와 papa에 대응되지만, hello에 대응되지 않습니다. )

 

(5) 와일드 카드 패턴과 함께 파일명의 집합이 주어질 때, 그중 패턴에 대응되는 파일명들을 찾아내는 프로그램을

작성하시오.

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 입력의 첫 줄에는 테스트 케이스의 수 C(1<=C<=50)

(2) 그 후 두 번째 줄에 와일드 카드 패턴 W는 알파벳 대소문자, 숫자와 *, ?만으로 구성

(3) 그 후 세 번째 줄에 문자열 개수 N(1<=N<=50)

(4) 그 후 네 번째 줄에 문자열 S(1<=S<=100)는 대소문자와 숫자만 구성과 공백 포함X

 

출력 조건

X

 

입력 예제

3
he?p
3
help heap helpp
*p*
3
help papa hello
*bb*
1
babbbc

 

출력 예제

help heap 
help papa 
babbbc 

 

 

 

 

3. 제약 조건

(1) 프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 한다.

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

X

 

 

 

 

6. 코드

: 이 문제에서는 세 가지의 코드가 존재한다.

 

먼저 (1)에서는 가장 쉽게 접근하는 완전 탐색을 보여준다.

또한 (2)에서는 (1)에서의 완전 탐색 중복 계산을 없애는 즉, 메모이제이션을 수행하는 것을 보여준다.

 

 

 

(1) 완전 탐색(Brute Force)

public class WILDCARD1 {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        int C = Integer.parseInt(sc.readLine());

        for(int i=0; i<C; i++) {
            String W = sc.readLine();
            int N = Integer.parseInt(sc.readLine());

            st = new StringTokenizer(sc.readLine());
            for(int y=0; y<N; y++) {
                String S = st.nextToken();
                if(solve(W, S)) {
                    sb.append(S+" ");
                }
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    private static boolean solve(String w, String s) {
        int pos=0;

        // 만약에 와일드 카드 패턴 위치가 '?' 이거나 패턴과 문자열이 같을 경우 
        // 현재 위치를 ++(통과)한다.
        while(pos<w.length() && pos<s.length() && (w.charAt(pos)=='?' || w.charAt(pos) ==s.charAt(pos))) 
            ++pos;

        // 만약 위치 값이 패턴 끝 값과 같다면, 
        // 문자열 또한 끝 값이 있는 지 확인
        if(pos==w.length()) return pos==s.length();

        // 패턴이 '*'로 시작하면 (pos+1)의 위치에서 재귀 호출한다.
        // 이때 문자열은 skip변수를 +1씩 올려서 해당 문자열 위치부터 재귀 호출한다.
        if(w.charAt(pos)=='*') {
            for(int skip=0; pos+skip<=s.length(); skip++) {
                if(solve(w.substring(pos+1), s.substring(pos+skip))) return true;
            }
        }
        return false;
    }
}

 

 

 

(2) 메모이제이션(Memoization)

public class WILDCARD2 {
	private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	
	private static String W, S;
	private static int[][] cache;

	public static void main(String[] args) throws IOException {
		StringTokenizer st;
		int C = Integer.parseInt(sc.readLine());
		
		for(int i=0; i<C; i++) {
			W = sc.readLine();
			int N = Integer.parseInt(sc.readLine());
			
			st = new StringTokenizer(sc.readLine());
			for(int y=0; y<N; y++) {
				cache = new int[101][101];
				
				S = st.nextToken();
				if(solve(0, 0)==1) {
					sb.append(S+" ");
				}
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
	
	// 0이면 논-캐시(초기상태)
	// 1이면 히트-캐시(캐시에 올라온 상태)
	// -1이면 노히트-캐시(캐시에 올라오지 않은 상태)
	private static int solve(int w, int s) {
		// 메모이제이션
		if(cache[w][s] != 0) return cache[w][s];

		while(w<W.length() && s<S.length() && (W.charAt(w)=='?' || W.charAt(w)==S.charAt(s))) {
			++w;
			++s;
		}

		if(w==W.length()) return cache[w][s] = (s ==S.length())?1:-1;

		if(W.charAt(w)=='*') {
			for(int skip=0; s+skip<=S.length(); skip++) {
				if(solve(w+1, s+skip)==1) return cache[w][s] = 1;
			}
		}
		return cache[w][s]=-1;
	}
}

 

 

 

 

7. 시간 복잡도 분석

- (1)과(2)는 내부에서 *를 찾으며 재귀 호출을 부르면서 발생하는 부분 문제 O(N^2)과 *에 몇 글자가 대응되어야

할지 검사하는 반복문 O(N)이 존재하기 때문에 O(N^3)이 나오게 된다.