[알고리즘문제] 프로그래머스 - 단어 퍼즐

같은 문자를 여러번 사용할 수 있다고 하였으니 재귀로 해결하는 방법을 생각해 보았다. tmp+=strs[n+1]를 계속하면서 tmp의 길이가 t보다 길면 재귀를 탈출하고 tmp+=strs[n+1]을 더하는 구조로 생각해 보았다. 하지만 틀렸다고 나왔고 다른 분의 풀이를 참고하였다. 2중 for문을 사용하여 dp로 최선의 값을 계속 갱신할 수 있다.

#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>

using namespace std;

int solution(vector<string> strs, string t)
{

    int answer = 0;
    set<string> s;
    vector<int> dp(t.length() + 1, INT_MAX);

    for (int i = 0; i < strs.size(); i++)
    {
        s.insert(strs[i]);
    }

    dp[t.length()] = 0;

    for (int i = t.length() - 1; i >= 0; i--)
    {
        string tmp = "";
        for (int j = i; j < t.length(); j++)
        {

            tmp += t[j];
            if (i + 5 < j)
                break;
            if (s.find(tmp) != s.end())
            {
                if (dp[j + 1] != INT_MAX)
                {
                    dp[i] = min(dp[i], dp[j + 1] + 1);
                }
            }
        }
    }

    answer = dp[0] != INT_MAX ? dp[0] : -1;
    return answer;
}

 

dp[2]은 apple의 "ple"를 만들 수 있는 최소의 단어개수를 의미한다. 이것을 우리는 2중 for문을 사용하여 구할 것이다.

 

i는 t.length()-1 부터 0까지 탐색하고,

j는 i부터 t.length()-1까지 탐색하면서 문자를 만들고(p,pl,ple) 그렇게 만든 문자가 set에 존재하면 dp[i]의 값을 수정해준다. 이때 수정하는 규칙은 dp[i]와 dp[j+1]+1둘 중 최소값을 선택하는데 dp[j+1]+1의 의미는, i~j까지 부분문자열이 set에 존재하기 때문에 이는 apple의 i~j의 문자열을 만드는데 하나만 필요하다는 뜻이다. 그렇기 때문에 j이후의 값 j+1와 i~j의 문자열을 더한 dp[j+1]+1를 해준다.

 

쉽게 설명하면, ple를 만들었을 때 pl이 set에 있기 때문에 pl(1가지 경우) + e를 만드는 경우의 수를 더한다는 의미이다.

 

그리고 세부적으로 만든 문자열이 set에 존재하는데 dp[j+1]가 INT_MAX인 경우는 만든 문자열과 j+1문자열이 서로 연결되지 않는 경우이기 때문에 제외한다. 또 단어 조각의 길이가 1~5이기 때문에 i+5 < j 인 경우는 제외한다.