[PCCP] Lv4: 단어 퍼즐(12983) 해설

문제

- 문제 링크: 단어 퍼즐

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: t의 길이

- t의 길이를 구할 때의 시간 복잡도: O(1)

- dp 리스트를 생성할 때 시간 복잡되 O(N)

- 이후 바깥쪽 반복문은 N번, 단어 조각의 길이는 최대 5이므로 안쪽 반복문은 최대 5번 반복되므로 Arrays.asList(strs).contains(sub)의 경우 최대 시간 복잡도는 O(5*100)

- 최종 시간 복잡도: O(N*5*5*100) → O(N)

import java.util.Arrays;
import java.util.HashSet;

class Solution {
    // 자바에서 상수 사이에 언더바(_)를 넣으면 언더바는 무시. 큰 숫자를 코드로 작성할 때 유용
    private static final int INF = 20_001;
    
    public int solution(String[] strs, String t) {
        int n = t.length(); // 타깃 문자열 t의 길이
        // 각 위치에서 필요한 최소 조각수를 저장할 배열(초기값은 INF로 함)
        int[] dp = new int[n + 1];
        Arrays.fill(dp, INF);
        // 빈 문자열을 위해 필요한 최소 조각수는 0
        dp[0] = 0;
        
        // strs 조각들의 길이를 저장한 해시셋
        HashSet<Integer> sizes = new HashSet<>();
        for (String str: strs) {
            sizes.add(str.length());
        }
        
        // dp[i]부터 dp[n]까지 채우기 위한 반복문
        for (int i = 1; i <= n; ++i) {
            // 각 str 조각의 문자열 길이에 대하여
            for (int size: sizes) {
                if (i - size >= 0) {
                    int idx = i;
                    String sub = t.substring(idx - size, idx);
                    // 이미 구한 해와 strs 조각을 추가해서 문자열을 만들 수 있다면
                    if (Arrays.asList(strs).contains(sub)) {
                        // 해당 위치의 최소 조각수를 갱신
                        dp[i] = Math.min(dp[i], dp[i - size] + 1);
                    }
                }
            }
        }
        // 최소 조각수를 반환
        return dp[n] < INF ? dp[n] : -1;
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: t의 길이

- t의 길이를 구할 때 시간 복잡도: O(1)

- dp 리스트를 생성: O(N)

- 바깥쪽 반복문은 N번, 단어 조각의 길이는 최대 5이므로 안쪽 반복문은 최대 5번 반복되므로 t[i - size: i] in strs의 경우 최대 시간 복잡도: O(5*100)

- 최종 시간 복잡도: O(N*5*5*100) → O(N)

def solution(strs, t):
    n = len(t) # 타겟 문자열 t의 길이
    dp = [float("inf")] * (n + 1) # 각 위치에서 필요한 최소 조각수를 저장할 배열(초기 값은 INF)
    
    dp[0] = 0 # 빈 문자열을 위해 필요한 최소 조각수는 0
    sizes = set(len(s) for s in strs) # strs 조각들의 길이를 저장한 집합
    
    for i in range(1, n + 1): # dp[i]로부터 dp[n]까지 채우기 위한 반복문
        for size in sizes: # 각 str 조각의 문자열 길이에 대하여
            # 이미 구한 해와 strs 조각을 추가해서 문자열을 만들 수 있다면
            if (i - size >= 0 and t[i - size: i] in strs):
                dp[i] = min(dp[i], dp[i - size] + 1) # 해당 위치의 최소 조각수를 갱신

    return dp[n] if dp[n] < float("inf") else -1 # 최소 조각수를 반환

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: t의 길이

- t의 길이를 구하는 시간 복잡도: O(1)

- dp 배열을 생성하는 시간 복잡도: O(N)

- 바깥쪽 반복문은 N번, 단어 조각의 길이는 최대 5이므로 안쪽 반복문은 최대 5번 반복되어 t[i - size: i] in strs의 경우 최대 시간 복잡도는 O(5 * 100)

- 총 시간 복잡도: O(N*5*5*100)

function solution(strs, t) {
    const n = t.length; // 타겟 문자열 t의 길이
    // 각 위치에서 필요한 최소 조각수를 저장할 배열(초기값은 INF로 함)
    const dp = Array(n + 1).fill(Infinity);
    dp[0] = 0; // 빈 문자열을 위해 필요힌 최소 조각수는 0
    // strs 조각들의 길이를 저장한 집합
    const sizes = new Set(strs.map((str) => str.length));
    
    for (let i = 1; i <= n; ++i) { // dp[i]부터 dp[n]까지 채우기 위한 반복문
        for (const size of sizes) { // 각 str 조각의 문자열 길이에 대하여
            // 이미 구한 해와 strs 조각을 추가해서 문자열을 만들 수 있다면
            if (i - size >= 0 && strs.includes(t.slice(i - size, i))) {
                dp[i] = Math.min(dp[i], dp[i - size] + 1); // 해당 위치의 최소 조각수를 갱신
            }
        }
    }
    
    return dp[n] === Infinity ? -1 : dp[n]; // 최소 조각수를 반환
}

solution 2)

import

solution 3)

import