[백준] S1 16500번 문자열 판별 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

16500번: 문자열 판별

[문제] 

알파벳 소문자로 이루어진 문자열 S와 단어 목록 A가 주어졌을 때, S를 A에 포함된 문자열을 한 개 이상 공백없이 붙여서 만들 수 있는지 없는지 구하는 프로그램을 작성하시오. A에 포함된 단어를 여러 번 사용할 수 있다.

[입력]

첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다.

[출력]

A에 포함된 문자열로 S를 만들 수 있으면 1, 없으면 0을 출력한다.

 

 

---

[풀이]

1. dp 배열을 만들어준다.

2. 뒤에서부터 탐색을 하여 subString으로 부분을 잘라 있으면 dp 배열을 1로 만들어 포함되는 것으로 표시해준다.

3. 이렇게 모든 부분을 체크해서 dp[0]이 1이라면 포함이 되는 것이고 아니라면 불가능한 것이다.

[접근]

1. replace를 사용해서 풀려고 접근을 하였다.

2. replace를 사용하면 중간에 바뀌고 나서의 문자가 겹쳐져서 지워지는 경우가 발생하는 것을 확인하였다.

3. 이후 어떻게 해야할 지 알아보다 dp를 사용해 문제를 해결한 것을 보고 참고하였다.

[코드]

package BOJ_silver;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main_S1_16500 {
	static int n;
	static String s;
	static int[] dp = new int[101];
	static Set<String> set = new HashSet<>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        s = br.readLine();
        n = Integer.parseInt(br.readLine());

        // 포함되는 단어인지 체크하기 위한 단어들 입력받기
        for (int i = 0; i < n; i++) {
            set.add(br.readLine());
        }

        for(int i = s.length() - 1; i >= 0; i--) {
            for(int j = i + 1; j < s.length(); j++) {
                if(dp[j] == 1) {
                	// 자른 문자열이 set에 포함되어 있다면 
                    if(set.contains(s.substring(i, j)))
                    	dp[i] = 1; // 1로 변경
                }
            }
            // 자르고 남은 부분 문자가 포함되어 있으면 1
            if(set.contains(s.substring(i)))
            	dp[i] = 1;
        }
        
        System.out.println(dp[0]);
    }
}