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

문제 링크

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

프로그래머스

완성시켜야 할 단어와 단어 조각들이 주어졌을 때, 원하는 단어를 완성시키기 위해 필요한 단어 조각의 수의 최소값을 리턴하자.

 

풀이

• 나의 처음 접근방식

나는 일단 특별한 방법이 떠오르지 않는 한, 일단 모든 경우의 수를 만들어보는 방식을 택한다.

백트래킹을 통해서 단어 조각들을 이어붙여서 단어를 만들어가는 방식이다.

만들어진 단어의 길이가 만들고 싶은 단어의 길이보다 크거나 같아졌을 때는 이제 비교를 하고 리턴을 해주어야한다.

만약 만들어진 단어의 길이가 만들고 싶은 단어의 길이보다 길다면 비교 할 필요도 없이 같지 않은 단어다.

만들어진 단어와 만들어야 할 단어가 같다면? 이때 사용된 조각의 개수를 현재 answer에 저장된 값과 비교해서 최소값을 answer에 저장한다.

 

아무래도 모든 경우를 따지다 보니, 시간이 오래걸려 시간초과를 받았다.

나름 시간을 줄이기 위해 2가지 장치를 넣어줬다.

1. 기존에 저장된 answer 보다 많거나 같은 단어조각을 사용했다면, 더 만들어볼 필요도 없이 리턴한다.

2. 단어 조각의 시작 알파벳을 기준으로 단어 조각을 분류해두었다.

만약 "banana" 라는 단어를 만드려고 하는데, 현재 "ban" 까지 만들어 졌다면 "ana" 만 만들어 주면 된다.

이때 단어조각을 이어붙일 때 모든 단어 조각을 이어붙여볼 필요는 없다. a로 시작하는 단어조각들 중에서만 이어붙여주면 경우의 수가 확 줄어들 것이다.

 

이렇게 나름 머리를 굴려봤지만, 시간초과는 피하지 못했다.

 

• 다른 사람들의 풀이

질문하기에 들어가봤더니, 사람들이 DP로 풀었다고 했다.

도저히 DP로 풀이할 방법이 떠오르지 않아서 구글에 있는 블로그들을 참고했다.

DP배열은 1차원 배열로 만든다.

DP[ i ] 에는 만들어야 할 단어의 i번째 인덱스까지 만드는데 필요한 최소 조각의 수를 저장한다.

만들어야 할 단어 문자열을 t라고 하고, 이용하고자 하는 단어 조각을 str이라고 한다면

t의 i번째 인덱스까지 만드는데 필요한 조각의 수 DP[ i ] 에 대한 식은 다음과 같다.

DP[ i ] = min( DP[ i - str.length()] + 1 , DP[ i ] ) 이다.

모든 단어 조각 str에 대해 해당 식이 성립하는 것이 아니다.

t 의 i - str.length() 번째부터 i번째 인덱스까지의 문자열과 str이 일치할 때만 위의 식이 성립한다.

 

앞의 예시와 같이 "banana" 라는 문자열을 만든다고 가정하자. 단어 조각에는 "ban"과 "ana"가 있다,

DP[ 3 ] 에는 "ban"을 만드는데 필요한 최소 조각의 수가 들어있다. "ban"이라는 조각이 있기때문에 DP[ 3 ] = 1 이다.

우리가 구해야 할 값은 최종적으로 DP[ 6 ]에 들어있는 값이다.

DP[ 6 ] 인 상황에서, 두 단어조각 "ban" 과 "ana"를 탐색해야한다.

첫번째 단어 조각 str = "ban" 인 경우, 6 - str.length()는 3이고 t의 3부터 5까지의 문자열 "ana"와 "ban"을 비교했을 때, 같지 않다. 만약 "ban"을 이용하면 "banban" 이라는 단어가 만들어지기 때문에 불가능한 경우다.

두번째 단어 조각 str = "ana" 인 경우, 6 - str.length() 는 똑같이 3이고 t의 3부터 5까지의 문자열 "ana" 와 단어조각 "ana"가 일치하기 때문에 위의 점화식을 사용해도 된다.

DP[ 6 ] = min(DP[ 6 - str.length()] + 1, DP[ 6 ] ) 이라는 식을 세울 수 있다. 이때 DP[ 3 ] = 1이기 때문에 DP[ 6 ] = 2가 된다.

 

이러한 방식으로 for( i = 1 ~ t의 길이) 까지 돌면서 DP[ i ] 값을 모두 채워주면 된다.

 

이때 문자열을 비교할때 ' == ' 을 사용하거나 compare 함수를 이용하면 시간초과를 받는다. 두 문자열을 비교하는 과정에서 시간이 많이 드는 듯 하다.

그냥 문자 하나하나 비교하는 게 더 시간적인 면에서 더 효율적이다.

 

코드 작성

#include <bits/stdc++.h>
using namespace std;
#define INF 20000 + 5
const int MAX_N = 20000 + 5;
vector<int> DP(MAX_N, INF);
 
int solution(vector<string> strs, string t)
{
    int answer = 0;
    DP[0] = 0;
    for(int i = 1; i <= t.length(); i++){
        for(auto str : strs){
            if(i < str.length())
                continue;
            if(DP[i - str.length()] == INF)
                continue;
            
            bool chk = true;
            for(int j = 0; j<str.length(); j++){
                if(t[i - str.length() + j] != str[j]){ //문자열 비교
                    chk = false;
                    break;
                }
            }
            //string temp = t.substr(i - str.length(), str.length());
            //if(!str.compare(temp))
            if(chk)
                DP[i] = min(DP[i], DP[i - str.length()] + 1);
        }
    }
    
    if(DP[t.length()] == INF)
        answer = -1;
    else answer = DP[t.length()];
    
    return answer;
}

문자열을 만드는 데에도 DP를 사용할 수 있는 걸 알게됐다.

DP 문제는 언제나 어렵다. 파이팅