Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 '단어 만들기 스티커' 문제 — 비트마스크 DP 완벽 정리

문제 이해하기

N개의 서로 다른 종류의 스티커가 있다고 가정해 봅시다. 각 스티커에는 하나의 소문자 영단어가 적혀 있으며, 우리는 스티커에서 글자를 하나씩 잘라내고 재배열하여 주어진 목표 문자열(target)을 완성해야 합니다.

여기서 중요한 조건은 다음과 같습니다.

  • 각 스티커는 필요한 만큼 여러 번 재사용할 수 있습니다.
  • 모든 종류의 스티커는 무한개씩 보유하고 있습니다.

목표는 target 문자열을 완성하는 데 필요한 최소 스티커 개수를 구하는 것입니다. 만약 어떻게 해도 완성할 수 없다면 -1을 반환합니다.

예를 들어 스티커가 ["dog", "sentence", "antenna"]로 주어지고, target이 "dance"라면 필요한 최소 스티커 수는 3입니다.

해결 접근 방식: 비트마스크 동적 계획법(DP)

이 문제는 target의 각 위치(인덱스)별로 글자가 채워졌는지 여부를 비트마스크로 관리하는 동적 계획법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • target의 길이를 n이라 할 때, n비트짜리 정수로 "지금까지 채운 글자 위치"를 표현합니다.
  • dp[i]는 상태 i(target에서 채워진 글자 집합)를 만들기 위해 필요한 최소 스티커 수를 의미합니다.
  • 각 스티커에 포함된 글자를 순회하면서, 아직 채우지 않은 target 위치에 해당 글자를 배치해 새로운 상태를 만들고 dp 값을 갱신합니다.

알고리즘 단계

  1. n := target의 길이
  2. N := 1을 n번 왼쪽 시프트한 값 (즉, 2^n)
  3. 크기가 N인 배열 dp를 선언하고 모든 값을 INF(무한대)로 초기화합니다.
  4. dp[0] := 0 (아무것도 채우지 않은 상태는 스티커 0장)
  5. i를 0부터 N-1까지 반복합니다.
    • dp[i]가 INF라면 도달할 수 없는 상태이므로 건너뜁니다.
    • j를 0부터 스티커 개수-1까지 반복합니다.
      • s := stickers[j], x := i
      • 스티커의 각 글자 z에 대해, target을 순회하며 target[l] == z이고 l번째 비트가 아직 0이라면 x의 l번째 비트를 1로 설정합니다(글자 하나당 한 위치에만 사용).
    • dp[x] := min(dp[x], dp[i] + 1)로 갱신합니다.
  6. 최종적으로 dp[N-1]이 INF면 -1을, 아니면 dp[N-1]을 반환합니다.

C++ 구현 코드

아래 예시 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
        int n = target.size();
        int N = 1 << n;
        vector <int> dp(N, INT_MAX);
        dp[0] = 0;
        for(int i = 0; i < N; i++){
            if(dp[i] == INT_MAX) continue;
            for(int j = 0; j < stickers.size(); j++){
                string s = stickers[j];
                int x = i;
                for(int k = 0; k < s.size(); k++){
                    char z = s[k];
                    for(int l = 0; l < target.size(); l++){
                        if(target[l] == z && ((x >> l) & 1) == 0){
                            x |= (1 << l);
                            break;
                        }
                    }
                }
                dp[x] = min(dp[x], dp[i] + 1);
            }
        }
        return dp[N - 1] == INT_MAX? -1 : dp[N - 1];
    }
};
main(){
    Solution ob;
    vector<string> v = {"dog", "sentence","antenna"};
    cout << (ob.minStickers(v, "dance"));
}

입력

["dog", "sentence","antenna"]
"dance"

출력

3

복잡도 분석

이 알고리즘의 시간 복잡도는 O(N × M × L × n)입니다. 여기서 N = 2^n(target 길이 기준 상태 수), M은 스티커 개수, L은 스티커 단어의 평균 길이, n은 target의 길이입니다. 공간 복잡도는 O(N)으로, 비트마스크를 활용해 지수적인 경우의 수를 효율적으로 압축하여 탐색할 수 있다는 점이 이 풀이의 핵심 강점입니다.