프로그래머스 - 2017 팁스타운 단어 퍼즐

문제 링크입니다 : https://programmers.co.kr/learn/courses/30/lessons/12983

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

 

동적계획법 문제였다.

 

나는 재귀적 동적계획법으로 구현했다.

 

동적계획법 구현시 짧은 길이의 단어보다 긴 단어를 먼저 구해줘야 정상적으로 작동할 것이다.

 

 

1. strs에 있는 단어 조각들을 길이순으로 정렬한다. 길이가 같은 경우에는 사전순으로 정렬한다. 그럼 딱 하나씩 시도 해보기 좋은 순서가 된다. (탐욕법)

 

 

2. 재귀함수를 돌면서 하나씩 끼워 맞춰본다. 각 재귀함수는 index - 1까지 글자가 채워져 있다고 가정하고 index번째 위치부터 가장 글자를 하나씩 끼워 맞춰본다. (완전 탐색)

재귀함수 한번 더 호출

 

한번 더 재귀함수 호출

 

 

재귀함수를 이용한 완전탐색

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define INF 987654321

using namespace std;

int getMinUse(const vector<string>& strs, const string& t, int index) {
    if(index == t.size()) return 0; // 기저 사례(재귀 함수 탈출 조건)
    
    
    int ret = INF; // 단어 t를 완성할 수 없는 경우 무한대를 반환하기 위해 INF로 초기화 한다.
    
    
    // index 위치의 글자를 완성하기 위해서 strs에 있는 글자들을 하나씩 끼워 맞춰본다.
    // index 위치에 strs[i]단어 길이을 댔을 때, 
    // t의 길이를 넘는다면 해보나 마나이다.
    for(int i = 0; i < strs.size(); i++) {
        if(strs[i].size() + index <= t.size()) {
            bool flag = true;
            for(int j = 0; j < strs[i].size(); j++) {
                if(t[index + j] != strs[i][j]) {
                    flag = false;
                    break;
                }
            }
            
            // flag : true (strs[i] 단어를 index 위치에 넣을 수 있는 경우)
            // strs[i] 단어의 길이 만큼 인덱스를 뒤로 이동 시켜시켜서
            // 나머지 부분도 재귀함수로 완성 시킨다.
            if(flag) {
                ret = min(ret, getMinUse(strs, t, index + strs[i].size()) + 1);
            }
        }
    }
    
    return ret;
}

bool compare(const string& a, const string& b) {
    if(a.size() == b.size()) {
        return a < b;
    }
    return a.size() > b.size();
}

int solution(vector<string> strs, string t)
{
    int answer = 0;
    
    sort(strs.begin(), strs.end(), compare);
    
    int result = getMinUse(strs, t, 0);
    
    if(result == INF) {
        answer = -1;
    } else {
        answer = result;
    }

    
    return answer;
}

이렇게 하면 당연히 시간초과로 문제가 해결되지 않는다.

 

이럴 때, 우리는 동적계획법을 사용해야한다.

 

 

 

 

 

(재귀적 동적계획법을 이용하면 다양한 동적계획법 문제들을 굉장히 직관적으로 해결할 수 있다. 혹시 재귀적 동적계획법과 순수함수 및 코드 작성법, 재귀적 동적계획법을 자세히 알고싶다면 댓글을 남겨주세요. 관련 글을 작성하고 대댓글 남겨서 알람 보내드리겠습니다.)

 

 

 

재귀적 동적계획법을 적용한 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define INF 987654321

using namespace std;

vector<int> cache;

int getMinUse(const vector<string>& strs, const string& t, int index) {
    if(index == t.size()) return 0;
    
    int& ret = cache[index];
    if(ret != -1) return ret;
    
    ret = INF;
    
    for(int i = 0; i < strs.size(); i++) {
        if(strs[i].size() + index <= t.size()) {
            bool flag = true;
            for(int j = 0; j < strs[i].size(); j++) {
                if(t[index + j] != strs[i][j]) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                ret = min(ret, getMinUse(strs, t, index + strs[i].size()) + 1);
            }
        }
    }
    
    return ret;
}

bool compare(const string& a, const string& b) {
    if(a.size() == b.size()) {
        return a < b;
    }
    return a.size() > b.size();
}

int solution(vector<string> strs, string t)
{
    int answer = 0;
    
    cache.assign(t.size(), -1);
    
    sort(strs.begin(), strs.end(), compare);
    
    int result = getMinUse(strs, t, 0);
    
    if(result == INF) {
        answer = -1;
    } else {
        answer = result;
    }

    
    return answer;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~