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

programmers.co.kr/learn/courses/30/lessons/12983

코딩테스트 연습 - 단어 퍼즐

- 접근법

먼저 문자열 처리 관련 문제를 접할때는, String 연산의 속도가 생각보다 많이 느리다는점을 유의해야한다.단순히 String 합 연산이나 Compare함수를 사용하더라도 자기가 생각한 로직의 시간복잡도에 더하여 시간초과가 나는 경우가 있다.

 

이 문제를 보면 각각 '무한'하게 주어지는 단어 퍼즐조각들을 이용하여 우리가 목표로 완성시킬 단어 t를 만들어야한다.그리고 그 단어t를 만들 수 있는 최솟값을 구하는 것이기 때문에 t[i]가 완성시킬 단어 t : i 번째 글자 라고 본다면각 i가 정점의 번호, t.length가 도착 정점이고, 0 (0글자)을 시작 정점으로 보고 BFS로도 접근 가능할 것이다.

 

하지만 다시 보면 더 간단하게 DP로 해결할 수 있음을 알수있다.

Dy[i] 를 완성시킬 단어 t의 i번째 글자까지 단어조각들로 만들 수 있는 최솟값이라고 하면

Dy[i] = Dy[i-이번에 조합할 단어조각의 단어길이]+1 이다.

 

ex) Dy[6]="banana"를 단어조각들로 만들 수 있는 최솟값     

     Dy[3]="ban"을 단어조각들로 만들 수 있는 최솟값     

          단어조각 "ana" 이라면     

     Dy[6]=Dy["banana"의 길이 6 - "ana"의 길이 3] + 1 (ana 사용);

 

점화식을 정리해보면 다음과 같다.

   Dy[i]= t[i]까지 만들 수 있는 최솟값

   Dy[i]=Dy[i]와 Dy[i-strs[j].length()]+1 중 최솟값

---

-소스코드

#include <iostream>
#include <string>
#include <vector>
#define INF 9999999
#define MINI(A,B) A>B ? B : A
using namespace std;
// Dy[i]= t[i]까지 만들 수 있는 최솟값
// Dy[i]=Dy[i-strs[j].length()]+1
int Dy[20002];
int solution(vector<string> strs, string t)
{
    bool flag=true;
    int answer = -1;
    int before_idx;
    for(int i=1;i<=t.length();i++) {
        Dy[i]=INF;
    }
    for(int i=1;i<=t.length();i++) {
        for(int j=0;j<strs.size();j++) {
            before_idx=i-strs[j].length();
            if(before_idx<0) continue;
            flag=true;
            for(int k=0;k<strs[j].length();k++) {
                if(t[before_idx+k]!=strs[j][k]) {
                    flag=false;
                    break;
                }
            }
            if(flag) {
                Dy[i]=MINI(Dy[i],Dy[before_idx]+1);
            }
        }
    }
    answer=Dy[t.length()];
    if(answer==INF) answer=-1;
    return answer;
}