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

문제

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

풀이

가장 긴 토큰부터 차례대로 검색해서 문자열을 완성하기 위해 깊이 우선 탐색(DFS)을 사용했다. 이후 시간 초과가 발생했고, pos 값을 상태로 정의할 수 있겠다는 생각에 메모이제이션을 적용했다.

지금 생각해보니 지금 로직은 Top-Down 방식의 동적 계획법(DP)이라고 볼 수 있는데, 뒤의 문자열부터 확인하며 반복문으로 체크하는 Bottom-Up 방식의 DP로 푸는 것이 더 나았을 것 같다.

소스 코드

C++17

#include <bits/stdc++.h>

struct Compare {
    bool operator()(const std::string &lhs, const std::string &rhs) const {
        if (lhs.size() == rhs.size()) {
            return lhs < rhs;
        }
        return lhs.size() > rhs.size();
    }
};

int solution(std::vector<std::string> strings, std::string target) {
    const size_t N = target.size();
    std::set<std::string, Compare> set(strings.cbegin(), strings.cend(), Compare());
    std::unordered_map<int, int> memo;

    std::function<int(const size_t)>
    dfs = [&] (const size_t pos) -> int {
        if (pos == N) {
            return 0;
        }

        if (memo.count(pos)) {
            return memo[pos];
        }

        int ret = -1;

        for (int length = 5; 0 < length; length--) {
            if (pos + length <= N && set.count(target.substr(pos, length))) {
                int next = dfs(pos + length);
                ret = (next == -1) ? ret
                    : (ret == -1) ? next + 1
                    : std::min(ret, next + 1);
            }
        }

        return memo[pos] = ret;
    };

    return dfs(0);
}

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

문제

풀이

소스 코드

Share this post