[Baekjoon] 백준 16500_문자열 판별 (Java)

16500번: 문자열 판별

 

문제 풀이

처음엔 단어목록(A)에 있는 단어들을 긴 단어부터 하나씩 문자열의 앞부분과 비교해서 일치하면 단어 길이만큼 삭제하고 다시 탐색하는 방식으로 접근했었는데, 단어목록에 software, soft 같이 단어 사이에 서브 스트링이 존재하는 경우 반례가 생기는 것 같다..(사실 정확한 문제점 발견 못함) 단어를 찾았다고 문자열에서 삭제한 후 다시 고려하지 않는 방식은 미처 고려하지 못하는 경우가 발생하는 것 같다. 따라서 DP 테이블을 이용해 문자열 내에서 단어목록에 있는 경우를 체크해 주는 방식으로 다시 접근했다.

 

DP 테이블에는 문자열 S에서 특정 인덱스 i부터 시작하는 서브 문자열이 단어목록에 존재하는 지에 대한 정보를 담고 있다. 단어목록에 있으면 1 없으면 0을 저장한다. 여기서 서브 문자열의 시작 위치인 i는 문자열 S의 끝에서 부터 앞으로 한 칸씩 순차적으로 이동하며 탐색한다. "그럼 시작하는 위치는 정해졌는데 각 서브 문자열의 끝 인덱스는??". 문제에서 공백없이 목록 속 단어들로만 연결되어 있는지 판단하라고 했다. 따라서 각 서브 문자열의 끝인덱스는 뒤에 있는 특정 단어의 바로 앞 또는 문자열의 맨 끝이 될 것이다.

위의 그림에서 보면 dp 테이블은 편의상 문자열의 끝을 쉽게 판단하기 위해 S의 길이 + 1로 지정하고 마지막 인덱스에는 1을 할당해줬다. 이제 S.length - 1부터 한 칸씩 앞으로 오며 서브 문자열을 구해 단어목록에 있는지 확인하자. 즉, "t", "st", "est", "test", "ntest", ... 이렇게 서브 문자열을 확인하는 작업을 할 것이다. i가 8일때, 서브 문자열의 시작은 c가 되고 마지막 문자는 14번의 t가 된다. 이렇게 구한 "contest"는 목록에 있으므로 dp[8]은 1로 채워준다. i가 6일 때는 r부터 뒤에 있는 다른 단어 (contest) 바로 앞인 e까지 "re"와 맨 끝까지인 "recontest"를 목록에서 확인하면 된다. (없으니 dp[6] = 0)

• 문자열의 서브 문자열을 구해 목록에 있는지 확인
• 서브 문자열의 시작은 i (문자열 S의 끝에서부터)
• 서브 문자열의 마지막은 j (뒤에 있는 다른 단어 앞 or 문자열 끝)
• 서브 문자열이 목록에 있다면 DP 테이블에 1로 표시

 

 

소스코드

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

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

        // 특정 인덱스에서 시작하는 단어가 "단어집합"에 있는지 없는지 판별
        // 0:없음 / 1:있음
        int[] dp = new int[str.length()+1];
        dp[str.length()] = 1;

    	// 단어들 집합
    	HashSet<String> set = new HashSet<>();
        int N = Integer.parseInt(br.readLine());
        for(int i = 0 ; i < N ; i++){
            set.add(br.readLine());
        }

    	// 문자열의 마지막 문자부터 체크
        for(int i = str.length() - 1 ; i>= 0 ; i--){     // 단어의 시작 인덱스
            for(int j = i+1 ; j <= str.length() ; j++){     // 단어의 끝 인덱스 찾기
                if(dp[j] == 1){                // 1로 표시되어있으면 끝으로 판단

                    // i부터 j까지 끊은 단어가 집합에 있는지 판별
                    if(set.contains(str.substring(i, j))){
                        dp[i] = 1;
                    }
                }
            }
        }

        System.out.println(dp[0]);
    }
}