프로그래머스 단어 퍼즐 JAVA 풀이 (DP, 시간복잡도)

🔗 문제 링크

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

---

📌 문제 개요

주어진 단어 조각들을 이용해 문자열을 완성하는 문제이다.
각 단어는 무한히 사용할 수 있으며, 최소 개수로 문자열을 구성해야 한다.

 

---

📌 접근 방법

• 문자열을 앞에서부터 구성하는 DP 문제
• dp[i]를 i까지 문자열을 만들 때 필요한 최소 단어 개수로 정의
• 단어 최대 길이가 5이므로 뒤에서 최대 5글자만 확인

---

📌 핵심 아이디어

문자열 최소 분할 문제 = DP

점화식 : dp[i] = min(dp[i - len] + 1)

 

조건 : t.substring(i-len, i) 가 strs 에 포함되어야 함

Set을 사용하여 탐색 최적화

---

📌 전체 코드

import java.util.*;

class Solution {
    public int solution(String[] strs, String t) {

        int n = t.length();
        int[] dp = new int[n + 1];

        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        Set<String> set = new HashSet<>(Arrays.asList(strs));

        for (int i = 1; i <= n; i++) {

            for (int len = 1; len <= 5; len++) {

                if (i - len < 0) continue;

                String sub = t.substring(i - len, i);

                if (set.contains(sub) && dp[i - len] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - len] + 1);
                }
            }
        }

        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
    }
}

 

---

🧾 정리

• 문자열 분할 + 최소 개수 → DP 문제
• 단어 길이 제한(최대 5)을 활용한 최적화가 핵심
• 시간복잡도 O(N)으로 효율성 통과 가능