691. Stickers to Spell Word - Streak 3

내 풀이 접근

설명이 복잡하지만, 읽어보면 결국 가장 작은 수 안에 target 문자들 전부 포함시키는 최소 단어 수를 구하는 문제이다.

이는 최단거리 문제와 유사하다.

• BFS
• DP

조건에서 추가로 최적화할 부분이 없나 탐색해보자.

• target.length <= 15이므로, 같은 단어를 15번 이상 넣을 이유는 없다.
  • 16^50
  • 너무 크다.

• 가장 부족한 단어부터 그리디하게 탐색하는 것이 최적해를 보장하나? -> X

• target.length <= 15이므로, 단어를 15개 이상 수집할 이유가 없다.
  • 중복조합 수식 (64 15)
  • 이것도 너무 크다.

• 그래프를 target에서 시작하면 어떨까?
  • 깊이 16
• 선택지 50가지가 맞나? 8가지여도 안되는데...(2^32)

• 결국 중요한건 남은 문자열 정보이다. 이를 활용해보자.
  • 이를 2^15로 표현하면?
    • 32768
  • 그래서 이걸 어떻게 활용하느냐...

여기서 차도가 없어 풀이를 봤습니다.

---

정해

백트래킹이었습니다~

핵심 아이디어 - 어차피 모든 단어를 포함해야 한다. 그러니 가장 앞에 있는 단어부터 탐색한다.

• 스티커별 알파벳 카운트를 미리 구한다. (int[26])
• 재귀 + 메모이제이션으로 remain(아직 만들어야 할 문자열)에 대해
  • 어떤 스티커를 하나 썼을 때 remain에서 얼마나 줄어드는지 계산하고
  • 남은 문자열로 재귀 호출하여 최소 개수를 구한다.
• 강한 가지치기
  • 현재 remain의 첫 글자를 하나라도 포함하지 않는 스티커는 건너뛴다(효과 없는 선택 제거).

class Solution {

    public int minStickers(String[] stickers, String target) {

        List<int[]> counts = new ArrayList<>();
        for (String s : stickers) {
            int[] c = new int[26];
            for (char ch : s.toCharArray()) c[ch - 'a']++;
            counts.add(c);
        }

        if (!isFeasible(counts, target)) return -1;
        Map<String, Integer> memo = new HashMap<>();
        memo.put("", 0);
        return dfs(target, counts, memo);
    }

    private int dfs(String remain, List<int[]> counts, Map<String, Integer> memo) {
        if (memo.containsKey(remain)) return memo.get(remain);
        int[] need = new int[26];

        for (char ch : remain.toCharArray()) need[ch - 'a']++;

        // 가지치기 기준 문자: 남은 문자열의 첫 글자
        char first = remain.charAt(0);
        int ans = Integer.MAX_VALUE;

        for (int[] c : counts) {
            if (c[first - 'a'] == 0) continue; 

            StringBuilder next = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                int left = need[i] - c[i];

                for (int k = 0; k < Math.max(0, left); k++) {
                    next.append((char) ('a' + i));
                }
            }
            String nextStr = next.toString();    
            int sub = dfs(nextStr, counts, memo);
            if (sub != -1) ans = Math.min(ans, 1 + sub);
        }
        int res = (ans == Integer.MAX_VALUE) ? -1 : ans;
        memo.put(remain, res);
        return res;
    }

    private boolean isFeasible(List<int[]> counts, String target) {
        int[] total = new int[26];
        for (int[] c : counts) {
            for (int i = 0; i < 26; i++) total[i] += c[i];
        }
        for (char ch : target.toCharArray()) {
            if (total[ch - 'a'] == 0) return false;
        }
        return true;
    }
}

이렇게 하면, 실제로 건너뛰는 단어가 많아 시간복잡도에 큰 무리 없이 답을 구해낼 수 있다.