[프로그래머스] 단어 퍼즐 풀이 과정 기록 (Python,Java)

 

처음시도 (틀린풀이)

def solution(strs, t):
    answer = 0
    INF = float("inf")
    n = len(t)
    
    dp = [INF] * (n + 1)
    dp[0] = 0
    
    for i in range(1, n + 1):
        for w in strs:
            if i >= len(w) and t[i-len(w):i] == w:
                dp[i] = min(dp[i],dp[i - len(w)] + 1)
    

    return dp[n] if dp[n] != INF else -1

dp[i]는 “문장 맨 앞에서부터 i번째 글자까지 완성하는 데 필요한 조각의 최소 개수”로 두었다.
문장의 각 위치마다, 사용할 수 있는 조각(str)이 있는지 살펴보고, 만약 끝이 맞는 조각이 있다면, 그 조각을 붙이기 전 단계에서 쓴 최소 조각 수에 1을 더해 최솟값을 확인하여 지금 위치까지 만들 수 있는 가장 적은 조각 수를 dp[i]에 저장했다.

 

말이 좀 어렵지만 결국엔 한 인덱스 나아갈때마다 각 단어집을 모두다뒤지는 애매한(?) 풀이이다..

 

이렇게하니

시간초과가 났다.

20,000 × 100 = 2,000,000. 이백만이니 시초 당연함...

 

 

정답풀이(수정후)

from collections import defaultdict

def solution(strs, t):
    answer = 0
    INF = float("inf")
    n = len(t)
    patterns = defaultdict(set)
    # 길이별로 strs 묶기
    for w in strs:
        patterns[len(w)].add(w)

    dp = [INF] * (n + 1)
    dp[0] = 0

    for i in range(1, n + 1):
        for L, sset in patterns.items():
            j = i - L
            # 가능한 조각 길이만 검사
            if j < 0 or dp[j] == INF:
                continue
            if t[j:i] in sset:
                dp[i] = min(dp[j] + 1, dp[i])

    return dp[n] if dp[n] != INF else -1

 

 

실패 원인: 매 위치마다 strs 전체(최대 100개)를 뒤져서 너무 많은 비교가 일어났다.

해결책:

• strs를 길이별로 묶어서(예: 길이 1짜리, 2짜리 …)
• 매 위치마다 실제로 필요한 길이만 검사하도록 줄였다..즉,가능한길이집합만 검사하도록함...
  예시로따지면 검사 횟수가 100 → 최대 5로 확 줄어들도록함.

이렇게 하니 통과했다.

 

 

JAVA풀이

// Map.Entry<Integer, Set<String>> e, computeIfAbsent(key, k -> new HashSet<>()).add(w);

public class P1882_퍼즐조각 {
    public int solution(String[] strs, String t) {
        int answer = 0;

        int n = t.length();
        int INF = n + 1;
        int[] dp = new int[n + 1]; // dp 초기화
        Arrays.fill(dp, INF);
        dp[0] = 0;

        // 길이별로 strs 묶기
        Map<Integer, Set<String>> patterns = new HashMap<>();
        for (String w : strs) {
            int L = w.length();
            patterns
                    .computeIfAbsent(L, k -> new HashSet<>())
                    .add(w);
        }

        // dp 채우기
        for (int i = 1; i <= n; i++) {
            for (Map.Entry<Integer, Set<String>> e : patterns.entrySet()) {
                int L = e.getKey();
                int j = i - L;
                if (j < 0 || dp[j] == INF) {
                    continue;
                }
                if (e.getValue().contains(t.substring(j, i))) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }

            }
        }

        return dp[n] == INF ? -1 : dp[n];
    }
}