[Algorithm] 프로그래머스 - 단어 퍼즐

https://school.programmers.co.kr/learn/courses/30/lessons/12983

접근

이 문제는 완전 탐색으로 해결할 수 없다.

strs 배열의 길이가 $1\leq{…}\leq{100}$ 이기 때문에, 순열을 계산하면 시간이 초과될 것이기 때문이다.

t의 길이 제한이 $1\leq{…}\leq{20,000}$ 이기 때문에 DP만 잘 정의하면,

t의 어느 자릿수까지를 만드는 데 필요한 최소 조각수를 구할 수 있다.

따라서, memoization을 위한 배열 dp를 i 길이의 문자열을 만드는 데 필요한 최소 조각 수로 정의한다.

소스코드(Java)

class Solution {
    public int solution(String[] strs, String t) {
        int[] dp = new int[t.length() + 1];
        for (int i = 1; i <= t.length(); i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;

        for (int i = 0; i < t.length(); i++) {
            if (dp[i] != Integer.MAX_VALUE) {
                for (String str : strs) {
                    if (t.startsWith(str, i)) {
                        int nextIndex = i + str.length();
                        dp[nextIndex] = Math.min(dp[nextIndex], dp[i] + 1);
                    }
                }
            }
        }

        return dp[t.length()] == Integer.MAX_VALUE ? -1 : dp[t.length()];
    }
}

 

최소값을 정의하는 배열이기 때문에 각 원소를 최댓값으로 먼저 설정해준다.

각 인덱스를 순회하며, 단어 조각을 끼웠을 때 완성되는 문자열에 드는 조각 갯수를 업데이트한다.

이걸 끝 인덱스까지 반복했을 때, 문자열 t의 길이가 dp에 한 번도 업데이트 되지 않았다면 이는 불가능한 조합으로 판단한다.