[Java] 단어 퍼즐 - Lv4 프로그래머스 / DP

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12983?language=java 

프로그래머스

 

 

 

풀이

DP를 사용하여 Bottom Up으로 풀이했고, 문제 예시에서의 banana로 예를 들어보자.

 

b

ba

ban

bana

banan

banana

 

dp배열의 각 idx는 위의 값들을 만족하는 최소값들로 채워나갔다.

strs의 원소에서, t의 인덱스마다 같은 substring이 있는지 확인하였고, 같다면 dp배열에 입력해나갔다.

//strs에서 선택한 문자열과 t의 부분이 일치하는지 확인
if(word.equals(t.substring(i - wordLength, i))) {
	//word하나로 현재까지의 문자를 만들 수 있을 경우ⓐ
    if(i - wordLength == 0) {
        dp[i] = 1;
        continue;
    }
    //이전에 만든 문자열이 있을 경우
    if(dp[i - wordLength] > 0) {
    	//dp[i]가 0일 경우, 이전 위치까지의 최소단어개수에서 + 1처리를,
        dp[i] = dp[i] == 0 ? dp[i - wordLength] + 1
        //dp[i]가 이미 채워져있다면(위의 ⓐ경우를 만족했던 경우. ex)ba, a)
        //둘 중 비교하여 작은 경우의 수를 입력
        : Math.min(dp[i], dp[i - wordLength] + 1);
    }
}

 

import java.util.*;

class Solution {
    public int solution(String[] strs, String t) {
        int tLength = t.length();
        int strsLength = strs.length;
        int[] dp = new int[tLength + 1];

        for(int i = 1; i < tLength + 1; i ++) {
            for(int j = 0; j < strsLength; j ++) {
                String word = strs[j];
                int wordLength = word.length();
                if(i - wordLength < 0) continue;

                if(word.equals(t.substring(i - wordLength, i))) {
                    if(i - wordLength == 0) {
                        dp[i] = 1;
                        continue;
                    }
                    if(dp[i - wordLength] > 0) {
                        dp[i] = dp[i] == 0 ? dp[i - wordLength] + 1 : Math.min(dp[i], dp[i - wordLength] + 1);
                    }
                }
            }
        }

        int answer = dp[tLength];
        if (answer == 0) return -1;
        return answer;
    }


    public static void main(String[] args) {
        Solution sol = new Solution();
        sol.solution(new String[]{"ba", "na", "n", "a"}, "banana");
    }
}