[백준] 16500번 : 문자열 판별 - 자바(Java)

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

16500번: 문자열 판별

 

문제 해석

알파벳 소문자로 이루어진 문자열 S가 있습니다

알파벳 소문자로 이루어진 단어 A가 있습니다.

 

이때 A에 포함된 단어목록을 한 개 이상 공백없이 붙여서 만들 수 있는지 없는지 구하는 프로그램을 작성하세요.

 

문자열 S의 길이는 100이하입니다.

A의 개수도 100개이하입니다.

 

문자열 S : softwarecontest

단어A : software, contest

 

단어A를 2개 붙이면 softwarecontest가 완성되기 때문에 만들 수 있으면 1출력

 

문제 풀이 전 설계

 

문자열 S가 100의 길이를 가지고 단어 100개가 각각 1개의 길이를 가지는 최악의 경우에 모든 경우를 탐색해보면

100^100의 시간복잡도가 나오게 됩니다.

 

느낌은 DP를 사용해야 할 것 같습니다.

 

문제 풀이

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

public class Main_16500_문자열판별 {

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

        //문자열 S 입력받기
        String s = br.readLine();
        //단어 N개
        int n = Integer.parseInt(br.readLine());

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

        int[] dp = new int[101];

        //뒤에서 부터 탐색시작
        for (int i = s.length() - 1; i >= 0; i--) {
            //i+1부터 끝까지 반복
            for (int j = i + 1; j < s.length(); j++) {
                //S[j~끝]까지 만들 수 있는 문자가 존재한다면
                if (dp[j] == 1) {
                    //S[i-j]까지 만들 수 있는 문자가 존재한다면
                    if (words.contains(s.substring(i, j)))
                        //DP[i] = 1 으로 변경 이는 S[i~끝]까지 만들 수 있음
                        dp[i] = 1; 
                }
            }

            // 자르고 남은 부분 문자가 포함되어 있으면 1
            // S의 뒷자리부터 0까지 순서대로 문자열을 substring으로 잘라 A에 속해있는지 확인한다.
            //ex) softwarecontest
            // t, st, est, test, ntest, ontest, contest .....
            //이때 contest가 words에 포함되었기 때문에 dp[8] = 1;
            if (words.contains(s.substring(i))) {
                dp[i] = 1;
            }
        }

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

 

 

 

 

 

 

 

 

출처

https://velog.io/@cchloe2311/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-16500.-%EB%AC%B8%EC%9E%90%EC%97%B4%ED%8C%90%EB%B3%84

[알고리즘] 백준 > #16500. 문자열판별