2022.03.06 71일차

백준 16500번 (문자열 판별)

문제

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

나의 풀이

1. 단어 목록에 해당하는 길이가 나오고 해당 단어와 일치할 경우 조건 만족
2. 문자열은 점점 증가시키면서 접근, 값은 기억해두기(조건 시작 위치)
3. 동적 계획법으로 접근, 이전 문자열 위치의 조건이 만족해야 함
4. 처음 문자열 조건 비교를 위해 배열 0에 true 할당, 길이 + 1

import java.io.*;
import java.util.*;

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());

        String[] A = new String[N];

        for (int i = 0; i < N; i++) {
            A[i] = br.readLine();
        }

        boolean[] checkArr = new boolean[S.length() + 1];
        checkArr[0] = true;

        for (int x = 0; x < S.length(); x++) {
            int length = x + 1;
            for (int z = 0; z < N; z++) {
                if (length >= A[z].length() && S.startsWith(A[z], length - A[z].length())) {
                    if (checkArr[length - A[z].length()]) {
                        checkArr[length] = true;
                        break;
                    }
                }
            }
        }

        int answer = checkArr[S.length()] ? 1 : 0;
        System.out.println(answer);
    }
}

생각하기

• 동적 계획법(DP) 접근 방식

  	1. 구하고자 하는 큰 문제를 작은 부분 문제로 나눈다. 
  	2. 가장 작은 부분 문제부터 풀이 후 값을 저장(종료 조건, 0 OR 1) => 메모이제이션
  	3. 메모이제이션된 부분 문제들의 해를 이용해서 순서대로 더 큰 상위 문제 답 풀이
  	4. 가장 큰 문제에 도달할때까지 반복

• startWith(searchString, toOffset)
  searchString: 탐색할 문자열
  toOffset: searchString을 탐색할 위치, 기본값 0
  반환값: true OR false