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

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 최솟값을 어떻게 찾을지만 고민하면 쉬운 문제다.

 

이전에 작은 문제들을 바탕으로 다음 문제를 해결하는 DP로 쉽게 풀 수 있는데, 왜냐하면 특정단어까지 만드는데 사용되는 최소횟수를 이용해 다음 문자까지 만드는데 사용되는 단어의 최소 횟수를 구할 수 있기 때문이다.

 

아래 그림을 보면

 특정 문자가 주어지면 그 문자의 i번쨰 문자를 만드는데 단어가 사용되는 최소 횟수가 적혀있다.

이제 d라는 문자까지 만드는데 사용되는 최소 횟수는 다음과 같이 구해 볼 수 있다.

 

1. a에 "bacd"라는 문자를 더하기

2. b에 "acd"라는 문자를 더하기

3. a에 "cd"라는 문자를 더하기

4. c에 "d"라는 문자를 더하기

 

여기서 중요한 점은 strs에 우리가 원하는 문자들이 있어야 된다.

반대로 말하면 strs에 있는 문자들만 꺼내서 a 뒤에 strs의 문자들을 붙일 수 있는지 비교한다.

그리고 a뒤에 문자를 붙였으므로 [a까지 만드는데 사용된 문자의 최소횟수+1]과 기존에 저장된 최소 횟수를 비교해서 최소 횟수를 저장하면 된다.

 

이렇게 이전에 계산한 결과는 항상 단어를 만드는데 사용 된 최소 횟수이기 때문에 [strs의 개수 * 문자열의 길이]의 시간으로 문제를 해결할 수 있다.

​

[아이디어 정리]

1. 특정 문자까지 만드는데 사용된 단어의 최소 횟수를 저장할 vector를 만든다.
2. 현재 단어까지 strs의 단어를 이용해 만들 수 있으면(즉, 저장된 최소 횟수가 -1이 아니라면) 현재 단어 뒤에 strs의 단어를 붙일 수 있는지 확인하고, 붙일 수 있다면 vector에 저장된 최소 횟수를 갱신한다.
3. 위 과정을 끝까지 반복해 최종적으로 마지막 vector에 저장된 값을 return한다.

 

 

Code

 

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool CanMake(int st, string &t, string cmpstr) // stidx부터 cmpstr개 비교한다.
{
    if (st+cmpstr.length()>t.length())
    {
        return false;        
    }
    for (int i=0; i<cmpstr.size(); i++)
    {
        if (cmpstr[i]!=t[st+i])
        {
            return false;            
        }        
    }
    return true;
}

int solution(vector<string> strs, string t)
{
    int answer = 0;

    vector<int> DP(t.length(),-1);
    for (int i=0; i<strs.size(); i++)
    {
        if (CanMake(0, t, strs[i]))
        {
            DP[strs[i].length()-1]=1;
        }
    }
    for (int i=0; i<DP.size(); i++)
    {       
        if (DP[i]!=-1)
        {
            for (int j=0; j<strs.size(); j++)
            {
                if (CanMake(i+1,t,strs[j]))
                {
                    if (DP[i+strs[j].length()]==-1)
                    {
                        DP[i+strs[j].length()]=DP[i]+1;                    
                    }
                    else
                    {
                        DP[i+strs[j].length()]=min(DP[i+strs[j].length()],DP[i]+1); 
                    }
                }                
            }            
        }   
    }

    return DP[t.length()-1];
}

 

---

 

이런 유형의 문제에 익숙해져서 그런가 보자마자 풀이가 쉽게 생각나는 문제였다

 

프로그래머스