[백준] 9996 한국이 그리울 땐 서버에 접속하지 - 문자열(String) + 정규표현식(Regular Expression) + 동적계획법(DP, Dynamic Programming) JAVA

https://www.acmicpc.net/problem/9996

9996번: 한국이 그리울 땐 서버에 접속하지

코드설명

문자열(String) + 정규표현식(Regular Expression) + 동적계획법(DP, Dynamic Programming)  문제입니다.

 

먼저 첫번쨰 방식은, 정규표현식을 사용합니다.

입력
1
a*b*c*d
abcd


결과값
DA

이 a*b*c*d 패턴이 주어졋을떄 정규표현식은 어떻게 생성하면 좋을까요?

아래와 같이 생성하면 됩니다.

^a[a-z0-9]*b[a-z0-9]*c[a-z0-9]*d$

의미는

^a : a로 시작하는 패턴입니다.

[a-z0-9]* : 영어소문자나 0-9까지의 숫자를 포함할 수 있습니다. 또한, * 로써, 0번이상 반복될 수 있습니다.

d$ : d로 끝나는 패턴입니다.

 

이 정규표현식에서 [] 에 대한 이해가 중요합니다.

기본적으로 []를 사용할경우 []안에 넣은 문자들 중 '하나'와 매치됩니다.

예로 들어 [a-z0-9] 라면 a-z에 있는 단어나 0-9에 있는 단어 1개를 의미합니다.

추가로, gr[ae]y는 'gray'와 'grey' 모두와 매치되지만, gray는 오직 'gray'와만 매치됩니다.

 

[]를 사용하지 않는 경우는 정확한 문자열 매치를 할때 사용합니다. 제 코드에서는 ^a와 같은 형태이겠네요.

코드

정답코드1입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.regex.Pattern;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int answer = 0;
	static String regExPattern, target;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		String str = br.readLine();
		
		regExPattern ="^";
		for(int i=0; i<str.length(); i++) {
			if(str.charAt(i) != '*') {
				regExPattern += str.charAt(i);
			}else if(str.charAt(i) == '*'){
				regExPattern += "[a-z0-9]*";
			}
		}
		regExPattern += "$";
		
		System.out.println(regExPattern);
		
		for(int i=0;i<N; i++) {
			if(Pattern.matches(regExPattern, br.readLine()) == true)
				System.out.println("DA");
			else
				System.out.println("NE");
		}
		
	}
	
}

정답코드2입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;
	public static String[] standard;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	
    	st = new StringTokenizer(br.readLine());
    	standard = new String[N];
    	standard = st.nextToken().split("\\*"); 
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		String temp = st.nextToken();
    		
    		if(standard[0].length() + standard[1].length() > temp.length() ) {
    			System.out.println("NE");
    			continue;
    		}
    		String compareFront = temp.substring(0, standard[0].length());
    		String compareBack = temp.substring(temp.length() - standard[1].length() ,temp.length());
    		
    		if(compareFront.equals(standard[0]) && compareBack.equals(standard[1])) {
    			System.out.println("DA");
    		}else {
    			System.out.println("NE");
    		}
    	}
    }

}

 

 

정답코드3입니다. 동적계획법을 적용한 코드입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int answer = 0;
	static String regExPattern, target;
	static int[][] cache = new int[101][101];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		regExPattern = br.readLine();
		
		for(int i=0;i<N; i++) {
			target = br.readLine();
			for(int j=0; j<101; j++) {
				Arrays.fill(cache[j],-1);
			}
			System.out.println(isDFS(0, 0) == 1 ? "DA" : "NE");
		}
	}
	
	static int isDFS(int pIdx, int tIdx) {
		if(pIdx == regExPattern.length() && tIdx == target.length()) return 1;
		if(pIdx >= regExPattern.length() || tIdx >= target.length()) return Integer.MAX_VALUE;
		if(cache[pIdx][tIdx] != -1) return cache[pIdx][tIdx];
		
		int ret = Integer.MAX_VALUE;
		if(regExPattern.charAt(pIdx) == '*') {
			ret = Math.min(ret, isDFS(pIdx, tIdx + 1));
			ret = Math.min(ret, isDFS(pIdx + 1, tIdx));
		}
		else if(regExPattern.charAt(pIdx) != '*' && regExPattern.charAt(pIdx) == target.charAt(tIdx)){
			ret = Math.min(ret, isDFS(pIdx + 1, tIdx + 1));
		}		
		
		return cache[pIdx][tIdx] = ret;
	}
		
	
}