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

문제 설명

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

문제 풀이

• DP를 이용하여 풀이하였다.
• 우선 HashSet 자료구조를 이용하여 후보 단어들을 저장하였다. (존재 여부 확인 O(1))
• 후보 단어들의 길이가 1이상 5이하인 점을 감안하여 다음과 같이 점화식을 정한다.

  dp[ind] = ind까지 단어를 구성 했을 때 사용한 최소 단어 개수
  dp[i] = MIN (dp[i-1] + 1, dp[i-2] + 1, dp[i-3] + 1, dp[i-4] + 1, dp[i-5] + 1)

• 위 점화식에서, MIN의 각 원소들이 배열 범위를 초과하지 않고 후보 단어에 t.subString(i-j, i+1)이 존재 하는 경우만 포함시켜줌.

소스 코드 (JAVA)

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {

    public Set<String> set = new HashSet<>();
    public int[] dp;

    public int solution(String[] strs, String t) {
        //초기화
        dp = new int[t.length()];
        set.addAll(Arrays.asList(strs));

        //dp 시작
        for (int i = 0; i < t.length(); i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < 5; j++) {
                if (i - j < 0) continue;
                if (!set.contains(t.substring(i-j, i + 1))) continue;
                if (i - j - 1 >= 0 && dp[i - j - 1] == Integer.MAX_VALUE) continue;
                min = Math.min(min, (i - j - 1 < 0 ? 0 : dp[i - j - 1]) + 1);
            }
            dp[i] = min;
        }

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