Algorithm/DP

BOJ#5015 ls

밤이2209 2017. 8. 7. 15:18

BOJ#5015 ls


* 문제

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




* 풀이


재귀 형태로 풀었습니다.


입력 파라미터는 패턴 문자열 P의 index인 p와 검사할 문자열 S의 index인 s입니다.


반환값은 memoization값인 dp[p][s]이며, dp[p][s]는 P[p]와 S[s]를 비교한 결과(매칭 여부)를 의미합니다. 


dp[p][s] = TRUE(1) or FALSE(0)

static int checkStringPattern(int p, int s)


일단 패턴은 와일드카드(*) 와 그 외 문자로 분류할 수 있습니다.



1. 와일드 카드(*)의 경우

와일드카드는 어떤 문자의 0개 또는 그 이상에 해당하므로 아래의 3가지 경우로 나누어 탐색할 수 있습니다.


  1) 0개에 해당하는 경우

if (checkStringPattern(p + 1, s) == TRUE)


  2) 1개에 해당하는 경우

if (checkStringPattern(p + 1, s + 1) == TRUE)


  3) 그 이상에 해당하는 경우

if (checkStringPattern(p, s + 1) == TRUE)


즉,


int isMatch = FALSE;

if (s <= sLength) {

    if (checkStringPattern(p + 1, s) == TRUE) isMatch = TRUE;
    if (checkStringPattern(p + 1, s + 1) == TRUE) isMatch = TRUE;
    if (checkStringPattern(p, s + 1) == TRUE) isMatch = TRUE;
}

return dp[p][s] = isMatch;



2. 패턴이 그 외 문자인 경우 무조건 패턴과 문자열을 비교해야 합니다.

if (P[p] == S[s]) return dp[p][s] = checkStringPattern(p + 1, s + 1);
else return dp[p][s] = FALSE;



* Test Case





* 나의 코드 (Java)

https://github.com/stack07142/BOJ/blob/master/BOJ%235015/src/Main.java


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

public class Main {

    static final int NONE = -1;
    static final int FALSE = 0;
    static final int TRUE = 1;

    // Pattern : P, File Name String :S
    static char[] P, S;
    static int pLength, sLength;

    static int[][] dp = new int[102][102];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        P = br.readLine().toCharArray();
        pLength = P.length;

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {

            S = br.readLine().toCharArray();
            sLength = S.length;

            initMemoization();

            if (checkStringPattern(0, 0) == TRUE) System.out.println(S);
        }
    }

    static int checkStringPattern(int p, int s) {

        // 종료 조건
        if (p == pLength && s == sLength) return TRUE;

        if (p >= pLength) return FALSE;

        if (s >= sLength && P[p] != '*') return FALSE;

        // Memoization
        if (dp[p][s] != NONE) {

            return dp[p][s];
        }

        // 탐색
        // Pattern : *
        if (P[p] == '*') {

            int isMatch = FALSE;

            if (s <= sLength) {

                if (checkStringPattern(p + 1, s) == TRUE) isMatch = TRUE;
                if (checkStringPattern(p + 1, s + 1) == TRUE) isMatch = TRUE;
                if (checkStringPattern(p, s + 1) == TRUE) isMatch = TRUE;
            }

            return dp[p][s] = isMatch;
        }
        // Pattern : . 또는 영어 소문자
        else {

            if (P[p] == S[s]) return dp[p][s] = checkStringPattern(p + 1, s + 1);
            else return dp[p][s] = FALSE;
        }
    }

    static void initMemoization() {

        for (int i = 0; i < 102; i++) {

            Arrays.fill(dp[i], NONE);
        }
    }
}


저작자표시 비영리 동일조건

'Algorithm > DP' 카테고리의 다른 글

BOJ#2294 동전 2  (0) 2017.09.12
BOJ#2698 인접한 비트의 개수  (0) 2017.08.08
BOJ#1234 크리스마스 트리  (0) 2017.07.12
BOJ#2167 2차원 배열의 합  (0) 2017.05.10
BOJ#1010 다리 놓기  (0) 2017.05.09

'Algorithm/DP'의 다른글

  • 현재글BOJ#5015 ls

관련글

티스토리툴바