[Java] 백준 16500번 - 문자열 판별

[문제]

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

16500번: 문자열 판별

[풀이]

 

아래의 블로그를 참고하였습니다. 

https://code-lab1.tistory.com/222

[백준] 16500번 문자열 판별 (자바 풀이)

 

DP로 풀이해야 한다는걸 생각해내지 못하고 결국 풀이를 참고하였습니다.ㅠㅠ

 

DP로 마지막 index부터 문자열을 잘라 substring을 생성하고, 해당 substring이 A의 집합 set에 포함되어있다면

dp[index] = 1로 갱신합니다. 또한 index + 1의 위치부터 dp 끝까지 탐색하며 1이 있다면 substring(index, 1이 있는 index)가 set에 존재한다면 dp[index] = 1로 갱신해줍니다.

 

예를 들어, s = "abcefg", set = { abc, efg, abce }이 입력으로 주어진다면 탐색 과정은 다음과 같습니다.

• f -> g가 1인지 확인 X
• e -> fg 중에 1이 있는지 확인 -> X (efg 가 set에 포함되어 있으므로 e의 index인 3에 1을 저장 : dp[3])
• c -> efg 중 e에 1이 있으므로, c의 index인 2부터 e의 index인 3까지의 substring인 c가 set에 존재하는지 확인 -> X

이러한 과정을 반복 하며 a에 도달했을때, bcefg중에 1이 있는 e를 기준으로 잡고 확인해본다면 substring(0,3)은 abc이고, abc는 set에 존재합니다 따라서 dp[0] = 1이 되고 반복문이 종료됩니다.

 

dp[0] = 1 이라는것은 문자열을 만들 수 있다는것을 의미하므로 1을 출력해주면 됩니다.

 

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int N = Integer.parseInt(br.readLine());

        // A 문자열을 입력 받음
        Set<String> set = new HashSet<>();
        for(int i=0;i<N;i++) {
            String word = br.readLine();
            if(s.contains(word)) {
                set.add(word);
            }
        }

        int[] dp = new int[s.length()];
        // 마지막 index부터 탐색
        for(int i=s.length() -1 ;i>=0;i--) {
            for(int j=i+1;j<s.length();j++) {
                if(dp[j] == 1 && set.contains(s.substring(i,j))) {
                    dp[i] = 1;
                }
            }
            if(set.contains(s.substring(i))) {
                dp[i] = 1;
            }
        }
        System.out.println(dp[0]);
    }
}