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

Kim Yuhyeon·2023년 8월 14일

알고리즘 + 자료구조

목록 보기

125/161

문제

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

접근 방법

DP 로 시도 !
ex. ["ba","na","n","a"] "banana" 3
1. DP 배열은 최대 숫자(INF) 로 초기화한다. (단, dp[0] = 0)
2. 1부터 t의 길이까지 부분 문자열을 뽑는다.
3. strs 단어 조각들을 각각 검사하면서 뒤에서부터 같은지 검사한다.

startIdx = 부분 문자열 길이 - 단어 조각 길이 -> 검사 시작 위치이다.

startIdx < 0 이면 당연히 같을 리가 없으므로 패스

ex. 부분 문자열 : "b"이고 단어 조각이 "ba"일 경우

1 - 2 = -1 (X)

startIdx - 단어 조각 길이 >= 0이면

ex. 부분 문자열 : "bana" 이고 단어 조각이 "na"일 경우

4 - 2 = 2 -> ba"na" 검사

각 문자를 검사하면서 같은지 본다.

다르면 pass

같다면

dp[len]을 dp[startIdx] + 1 과 dp[len] 중 최솟값으로 갱신한다.

dp배열을 모두 갱신했다면 dp[t.length()]의 값을 본다.

값이 INF 면 단어 조각으로 조합이 불가능한 경우이므로 -1

아니면 dp[t.length()] 출력

풀이

#include <iostream>
#include <string>
#include <vector>

#define INF 987654321
#define MAX 20004

using namespace std;

int dp[MAX]; 

void Init()
{
    for(int i=1; i<MAX; i++)
    {
        dp[i] = INF;
    }
}

int solution(vector<string> strs, string t)
{
    
    // 배열 초기화 
    Init();
    
    int answer = -1;
    
    // 1부터 t의 길이까지 부분 문자열을 뽑는다.
    for(int len=1; len<=t.length(); len++)
    {
        
        string subStr = t.substr(0, len);
        
        // 단어 조각
        for(string word : strs)
        {
            // 시작 인덱스 (ex. bana(4) - na(2) - 2 > 0)
            int startIdx = len - word.length(); 
            
            // 길이가 크면 패스
            if (startIdx < 0)
                continue;
            
            // 길이가 작거나 같으면 완전히 같은 지 검사
            // ba"na" == "na" ? 
            bool isSame = true;
            
            for(int i=0; i<word.length(); i++)
            {
                if (subStr[startIdx + i] != word[i])
                {
                    isSame = false;
                    break;
                }
            }
            
            // 같지 않으면 패스
            if (!isSame)
                continue;
                        
            dp[len] = min(dp[len], dp[startIdx] + 1);
        }
    }
 
	
    
    // 갱신이 되었다면 리턴 
    if (dp[t.length()] != INF)
        answer = dp[t.length()];
    
    return answer;
}