[종만북][알고스팟] 와일드카드 (WILDCARD) - 동적계획법(Dynamic Programming) JAVA

passionfruit200 2024. 6. 8. 01:26

2024. 6. 8. 01:26

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

algospot.com :: WILDCARD

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

www.algospot.com

코드설명

동적계획법(Dynamic Programming) 문제입니다.

먼저 일반 완전탐색 재귀함수로 실행하는 경우입니다.

이 경우의 종료조건입니다.

1.. s[pos]와 w[pos]가 대응되지 않는다. : 서로 다르면 당연히 대응실패입니다.

2. pos가 w의 끝에 도달했다. : 패턴에 남은 *이 하나도 없는 경우입니다.이 경우에 패턴과 문자열의 길이가 정확히 같아야만 패턴과 문자열이 대응됩니다.

3. pos가 s의 끝에 도달했다 : 패턴은 남았지만 문자열이 이미 끝난 경우입니다. 당연히 대응실패라고 생각할 수 있지만, 남은 패턴이 전부 *로 구성되어있다면 두 문자열은 대응될 수 있습니다. 이 경우를 제외하고는 답은 항상 거짓입니다.

4. w[pos]가 *인 경우 : *가 몇 글자에 대응될지 모르기 때문에, 0 글자부터 남은 문자열의 길이까지를 순회하며 모든 가능성을 검사합니다. 이떄 w의 pos + 1 이후를 w'라 하고, s의 pos + skip 이후를 문자열 s'으로 해서 match(w', s')로 재귀호출 했을떄 답이 하나라도 참이면 답은 참이 됩니다.

위의 완전탐색 코드는 각 *에 대응되는 글자 수의 모든 조합을 검사합니다. 예시로 ******a와 aaaaaaaab와 같은경우 이 문제는 절대 맞을 수 없음에도 패턴에 *가 있을때마다 s에 남은 문자열의 모든 경우의 수를 검사하고 있습니다.

만약 이 코드가 실행되는 과정에서 수행하는 계산의 대부분이 여러 번 중복으로 이루어진다면, 입력이 주어졌을떄 답을 저장하는 캐시를 이용하여 프로그램의 중복계산을 피합니다.

동적계획법을 활용할 경우입니다.

어떻게 중복계산이 얼마나 일어나는지 알 수 있을까요?

중요한 단서는 입력으로 주어지는 w와 s의 종류는 제한되어 있다는 것 입니다. 재귀 호출할떄 우리는 항상 w와 s의 앞에서만 글자들을 떼내기 떄문에 w와 s는 항상 입력에 주어진 패턴 W와 파일명 S의 접미사(suffix)가 됩니다. 따라서 입력으로 주어질 수 있는 w와 s는 각각 최대 101개밖에 없습니다. (문자열의 길이는 각각 최대 100개입니다.) 이떄 match()가 101x101 = 10201번 이상 호출되었다면 비둘기 집의 원리에 따라 어떤 부분문제가 반드시 여러번 계산되고 있다는 뜻 입니다.

메모이제이션을 활용할경우, w는 항상 전체 패턴 W의 접미사이기 때문에 w의 길이가 결정되면 w또한 결정됨을 알 수 있습니다. 이 점을 이용하면 101x101 크기의 cache 배열에 모든 부분 문제의 답을 저장할 수 있습니다.

시간복잡도는 O(N^3)이 됩니다.

세번째는, 재귀문에서 반복문을 제거하는 경우입니다.

결국 반복문과 재귀문은 같은 역할을 하기에 재귀문으로만 만들 수 있습니다.

시간복잡도는 반복문이 사리지기에 O(N^2)이 됩니다.

하지만 실제로는 재귀함수가 실행되며 함수스택이 메모리에 많이 할당되고 해제되면서 시간은 크게 차이나지 않습니다.

실제로 구현하며 틀렸었던 부분은

기저사례에서 만약 W.Length()와 S.LENGTH()를 넘어간다면 바로 실패처리하는것이 틀렸습니다.

아래는 틀린 코드입니다. *p* 와일드패턴과 같이 마지막에 '*' 가 있는 경우가 처리하기 복잡하므로, 재귀를 호출하는 부분에서 길이가 조건에 맞을때(W < W.length() , fIdx < FileName.length()) 이런식으로 항상 문자 길이 이내에 있을떄만 호출하도록 재귀 호출 부분에 조건문을 두어서 원활하게 처리합니다.

public static int isMatch(int wildCardIdx, int fileNameIdx) {
    //기저사례 : 만약 wildCardIdx와 fileNameIdx 둘다 끝까지 갔다면 성공한 것 이다.
    if(wildCardIdx == W.length() && fileNameIdx == fileName.length()) {
        return 1;
    }

    //기저사례 : 만약 wildCard 혹은 fileName 둘중 하나라도 혼자 끝난다면 실패이다.
    if(wildCardIdx >= W.length() || fileNameIdx >= fileName.length()) {
        return Integer.MAX_VALUE;
    }
    ...

이유는 *p* 에서, help로 보면 이해가 갈 것 입니다. 마지막 *p*에서 이미 help는 끝난상태인데, 이 기저사례에서 처리되므로 wildCardIdx는 더 이상 이동하지 못했습니다.
wildCardIdx가 다음 *p*에서 length 3으로 도달하기 전에 즉, isMatch(wildCardIdx + 1, fileNameIdx)가 실행되기 전에 fileNameIdx는 이미 >= fileName.length()이므로 안되는것과 같습니다.

코드

완전탐색 재귀함수 실행경우입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static ArrayList<String> answer = new ArrayList<>();
	public static int[][] map;
	public static int[][] cache;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		while(C-- >0) {
			st = new StringTokenizer(br.readLine());
			String wildcardW = st.nextToken();
			answer.clear();
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				String fileName = st.nextToken();
				if(match(wildcardW, fileName) == true) {
					answer.add(fileName);
				}
				
			}
			Collections.sort(answer);
			for(String a : answer) {
				System.out.println(a);
			}
			
		}

	}
	
	//와일드카드 패턴 w가 문자열 s에 대응되는지 여부를 반환한다.
	public static boolean match(String w, String s) {
		//기저 사례 불필요함.
		//이유는  만약 w의 길이가 0일경우, s가 0일경우가 기저사례가 될 수 있는데 이미 아래에서 처리하고있습니다.
		//w.charAt(pos) !=와 s.charAt(pos) 일경우, 이미 해당 와일드카드는 실패패턴입니다.
		//w.charAt(pos) =='?" 일경우 PASS입니다.
		//하나하나 재귀로 실행하기보다는 패턴에 맞는 부분은 넘어가는 처리를 합니다.
		
		//w[pos]와 s[pos]를 맞춰나간다.
		int pos = 0;
		while(pos < w.length() && pos < s.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;
	}
	
}

완전탐색 재귀함수 코드 2입니다. 살짝 다릅니다. 모든 경우를 재귀로 처리합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = 0;
	public static String W, fileName;
	public static ArrayList<String> answerArr = new ArrayList<>();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		while(C-- >0) {
			st = new StringTokenizer(br.readLine());
			W = st.nextToken();
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			answerArr.clear();
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				fileName = st.nextToken();
				if(isMatch(0, 0) == 1) {
					answerArr.add(fileName);
				}
				
			}
			Collections.sort(answerArr);
			for(String s : answerArr) {
				System.out.println(s);
			}
		}
		
	}
	
	public static int isMatch(int wIdx, int fIdx) {
//		System.out.println("wIDx:"+wIdx+"fIdx:"+fIdx);
		//기저사례 1 : 만약 두개 모두 문자열 끝까지 도착했다면
		if(wIdx == W.length() && fIdx == fileName.length()) {
			return 1;
		}
		
		int ret = Integer.MAX_VALUE;
		//만약 '?' 라면 한문자씩 둘다 넘어갑니다.
		if( wIdx < W.length() && fIdx < fileName.length() && W.charAt(wIdx) == '?' ) {
			ret = Math.min(ret, isMatch(wIdx + 1, fIdx + 1));
		}
		//만약 '문자'가 같다면, 한 문자씩 둘다 넘어갑니다.
		else if( wIdx < W.length() && fIdx < fileName.length() && W.charAt(wIdx) == fileName.charAt(fIdx)) {
			ret = Math.min(ret, isMatch(wIdx + 1, fIdx + 1));
		}
		//만약 '*'라면,
		//	1. 와일드패턴 1칸 이동, 파일네임은 그대로.
		//	2. 와일드패턴은 그대로. 파일네임은 1칸 이동.
		else if( wIdx < W.length() && W.charAt(wIdx) == '*') {
			//아래의 경우 if else if 가 아니라 if if문으로 처리해서 2가지 모두 가능한경우 실행해야만 합니다.
			if( wIdx < W.length()) {
				ret = Math.min(ret, isMatch(wIdx + 1, fIdx));
			}
			if( fIdx < fileName.length()) {
				ret = Math.min(ret, isMatch(wIdx, fIdx + 1));
			}
		}
		
		return ret;
	}
}

동적계획법을 활용하는 경우입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static ArrayList<String> answer = new ArrayList<>();
	public static int[][] map;
	//-1은 아직 답이 계산되지 않았음을 의미합니다.
	//1은 해당 입력들이 서로 대응됨을 의미합니다.
	//0은 해당 입력들이 서로 대응되지 않음을 의미합니다.
	public static int[][] cache;
	public static String W, S;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		while(C-- >0) {
			st = new StringTokenizer(br.readLine());
			String wildcardW = st.nextToken();
			answer.clear();
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				String fileName = st.nextToken();
				W = wildcardW;
				S = fileName;
				cache = new int[101][101];
				for(int idx=0; idx<101;idx++) {
					Arrays.fill(cache[idx], -1);
				}
				
				if(matchMeorized(0, 0) == 1) {
					answer.add(fileName);
				}
			}
			Collections.sort(answer);
			for(String a : answer) {
				System.out.println(a);
			}
			
		}

	}
	
	//와일드카드 문제를 해결하는 동적계획법 알고리즘
	//와일드카드 패턴 W[w..]가 문자열 S[s..]에 대응되는지 여부를 반환한다.
	public static int matchMeorized(int w, int s) {
		//메모이제이션
		if(cache[w][s] != -1) return cache[w][s];
		
		//W[w]와 S[w]를 맞춰나갑니다.
		while(s < S.length() && w < W.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() == true ? 1 : 0 ))) ;
		
		//4. *를 만나서 끝난경우 : *에 몇글자를 대응해야 할지 재귀 호출하면서 확인한다.
		if(W.charAt(w) == '*') {
			for(int skip = 0; skip + s <= S.length(); skip++) {
				if(matchMeorized(w + 1, s + skip) == 1) {
					return cache[w][s] = 1;
				}
			}
		}
		
		//3. 이외의 경우에는 모두 대응되지 않습니다.
		return cache[w][s] = 0;
	}
	
	
}

재귀함수에서 반복문을 제거한 코드입니다. 더 코드가 직관적입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static ArrayList<String> answer = new ArrayList<>();
	public static int[][] map;
	//-1은 아직 답이 계산되지 않았음을 의미합니다.
	//1은 해당 입력들이 서로 대응됨을 의미합니다.
	//0은 해당 입력들이 서로 대응되지 않음을 의미합니다.
	public static int[][] cache;
	public static String W, S;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		while(C-- >0) {
			st = new StringTokenizer(br.readLine());
			String wildcardW = st.nextToken();
			answer.clear();
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				String fileName = st.nextToken();
				W = wildcardW;
				S = fileName;
				cache = new int[101][101];
				for(int idx=0; idx<101;idx++) {
					Arrays.fill(cache[idx], -1);
				}
				
				if(matchMeorizedWithNoIteration(0, 0) == 1) {
					answer.add(fileName);
				}
			}
			Collections.sort(answer);
			for(String a : answer) {
				System.out.println(a);
			}
			
		}

	}
	
	
	//와일드카드 패턴 W[w..]가 문자열 S[s..]에 대응되는지 여부를 반환한다.
	public static int matchMeorizedWithNoIteration(int w, int s) {
		//메모이제이션
		if(cache[w][s] != -1) return cache[w][s];
		
		//W[w]와 S[w]를 맞춰나갑니다.
		while(s < S.length() && w < W.length()
				&& (W.charAt(w) == '?' || W.charAt(w) == S.charAt(s) )) {
			return cache[w][s] = matchMeorizedWithNoIteration(w + 1, s + 1);
		}
		
		//더이상 대응할 수 없으면 왜 while문이 끝났는지 확인합니다.
		//2. 패턴 끝에 도달해서 끝난 경우 : 문자열도 끝났어야 합니다.
		if(w == W.length()) return ( cache[w][s] = ( (s == S.length() == true ? 1 : -1 ))) ;
		
		//4. *를 만나서 끝난경우 : *에 몇글자를 대응해야 할지 재귀 호출하면서 확인한다.
		if(W.charAt(w) == '*') {
			if(matchMeorizedWithNoIteration(w + 1, s) == 1 ||
					(s < S.length() && (matchMeorizedWithNoIteration(w, s + 1) == 1)) ) {
				return cache[w][s] = 1;
			}
		}
		
		//3. 이외의 경우에는 모두 대응되지 않습니다.
		return cache[w][s] = 0;
	}
	
}

'알고리즘 > 알고리즘 문제해결 전략(종만북) & 알고스팟' 카테고리의 다른 글

[종만북][알고스팟] 최대 증가 부분 수열 (LIS) - 동적계획법(Dynamic Programming) JAVA (0)	2024.06.08
[종만북][알고스팟] 삼각형 위의 최대 경로 (TRIANGLEPATH) - 동적계획법(Dynamic Programming) JAVA (0)	2024.06.08
[종만북][알고스팟] 외발 뛰기 (JUMPGAME) - 동적계획법(Dynamic Programming) JAVA (0)	2024.06.07
[종만북] 이항 계수 - 동적계획법(Dynamic Programming) JAVA (0)	2024.06.07
[종만북][알고스팟] 쿼드 트리 뒤집기 - 분할정복(DivideandConquer) JAVA (0)	2024.05.31

passionfruit200