[JAVA] 프로그래머스 단어 퍼즐

🤔 풀기 전의 문제에 대한 생각

☑️ 문제를 읽으며

주어진 STR 문자 배열을 사용해서 최솟값으로 원하는 문자열을 완성

처음 봤을때 아예 생각이 떠오르지 않는 문제

생각한 추상적인 접근법

접근법

1. 해당 문자열의 자릿수의 DP

문자열이 주어졌을때 apple이라고 치면 a까지의 가능한 최솟값을 기준으로

주어진 STRS 문자열 배열을 SET으로 전환시켜 contains 확인하는 식으로 가면 어떨까??

2.문자열의 시작을 찾는다.

1. 우선 문자열의 시작을 이룰수 있는 문자열을 찾는다.
   1. N번 순회해서 시작을 이룰수 있는 문자열 찾기
2. 시작을 이루는 문자열을 기준(최대 100개)잡기
   1. 남은 문자열을 기준으로 문자열을 잘라가면서 set에 contains인지 확인

작성하다보니 둘다 안되는 것같다.

🥸단순하게 생각하자

DP는 결국 점화식을 구해서 초기값을 정하고 반복문을 돌려서 푸는 문제라고 생각한다.

문제에서 요구하는 내가 정의해야 되는 DP는 무엇일까?

작은 문제로 분해해서 그 작은 문제로 결과적으로 최종 답을 구해야 한다.

초기화한 DP값과 낮은 단계의 DP값을 활용해서 최종 답……

문제의 목표 : 단어 조각을 활용해서 문장을 최솟값으로 완성해야된다.

1. 주어진 STR배열에서 하나를 사용해서 몇개를 써야되나 → 확장해서 다 사용하면 ?

도지히 모르겠네..

답을 봤고 설명에서 이어서..

🧶 예상 시간 복잡도

✅ 코드

import java.util.*;

class Solution {
    static int INF = 20_001; // 문자열의 최대길이가 20000 이기에
    public int solution(String[] strs, String t) {
        // 조각 문자를 Set에 넣기
        HashSet<String> set = new HashSet<>(Arrays.asList(strs));
        // 조각 문자열 사이즈 넣기 
        HashSet<Integer> sizes = new HashSet<>();
        for (int i = 0 ; i < strs.length; i++){
            sizes.add(strs[i].length());
        }
        // 최소조각수 저장 DP 배열 선언 
        int[] dp = new int[t.length()+1];
        Arrays.fill(dp,INF);
        dp[0] = 0;
        for (int len = 1; len <= t.length(); len++){
            // 조각 문자의 길이만 고려
            for (int size : sizes){
                if (len-size >= 0) {
                    String piece = t.substring( len - size , len );
                    if (set.contains(piece)) dp[len] = Math.min(dp[len],dp[len - size] + 1);
                }
            }
        }
        return dp[t.length()] == INF ? -1 : dp[t.length()];
    }
}

📔 설명 및 정리

💡 설명

우선 어려운 DP 문제를 풀때 접근하는 방식에 대해서 다르게 생각하게 되었다.

한번에 점화식을 정의하고 문제를 풀려하기 보다는 Brute Force로 푸는 방법을 생각하고, 성능을 최적화해보자.

접근법

1. Brute Force 방식 일단 어떻게든 풀어볼 수 있는 방법을 생각해보자.
2. 그 방식의 성능을 최적화해서 시간복잡도를 맞추자.

1. 어떻게든 풀기

주어진 문제에서 보면 결국 banana라는 문자열을 최솟값으로 만들어가기 위해서

맨 앞 문자열부터 즉 b ba ban이런식으로 앞부터 읽어가면서 해당 문자열을 완성하는 최솟값을 갱신한다.

bana를 만들려면 b ba ban에 대한 최소 문자열 값이 이미 구해져있는 것.

예를 들어본다면 bana를 처음부터 만들고 주어진 문자열은 ba ,n, a, na 이렇게 있다고 보자.

DP배열은 초기에 INF값 (아주 큰 값)으로 초기화한다.

b를 만들기 위한 문자열은 존재하지 않기에 INF값 그대로 둔다.

ba를 만들기 위해서 ba가 존재하기에 1로 갱신한다.

ban를 만들기 위해서 b + an 의 경우의 수와 ba + n의 경우의수를 본다 ba+n이 있기에 ba + n 2로 갱신

bana을 만들기 위해서 b+ ana or ba+na or ban+a 여기서 최소로 선택되는 값은 무엇일까

ba + na이다 ba값은 1이고 na라는 문자열로 갱신이 가능하기에 총 답은 2인것이다.

ban + a 도 가능하지만 3개의 문자열을 사용해야하기에 안된다.

이러한 과정을 거치고 나면 우리는 규칙을 발견할 수 있다.

1. 해당 문자열이 조각에 존재하는지
2. 없다면
   1. 이전 조각수를 활용 가능한지
      1. 가능하면 조각수들중 최소조각수 + 1

시간 복잡도

이런 방식으로 풀게되면 20,000개의 문자열을 앞에서부터 N^2번 반복해서 풀어야 된다.

총 400 000 000 4초 이상 터진다.

2. 효율적으로 성능 최적화 하기

여기서 시간을 소요하는 부분은 bana을 만들때 b+ ana or ba+ na or ban+a 이렇게 경우를 다 보는 것이다.

여기서 우리는 조각문자열의 길이를 활용해서 부분조각수에 문자열을 더해서 만들수있는지 확인하는 것이다.

즉 b + ana에서 우리에게 주어진 조각문자는 ba na a n 이렇게만 있다고 가정시 길이가 3인 조각문자는 없기에 스킵하는 것이다.

이런식으로 구성하면 비용을 줄일 수 있다.

주어진 문자열의 길이가 Len 이라고 할시 Len - (조각문자의 길이) ≥ 0 ⇒ 음수가 되면 당연히 안되기에

주어진 문자열에서 Len- (조각문자길이) , Len까지 substring한 문자가 조각문자에 포함되어있는지 확인하는 것.

이렇게만 해도 주어진 조각 문자의 길이 부분인 1 , 2 ,3 ,4, 5 총 5가지만 확인하면 된다는 것이다.

점화식

1. 앞에서 부터 추가할 조각의 사이즈를 고려한다.
   1. 문자열 조각이 존재하면
      1. 문자열 조각 1개과 더해서 문자열을 완성가능한 최소조각수를 더한 값이 최솟값 후보가된다.
      2. ex) bana를 완성시 ba na 이 방법 은 dp[ Len(4) - 2(조각사이즈)] + 1 값이 후보가 될수있다.
      3. ex) ban + a ⇒ dp[ Len - 1 ] + 1값이 후보가 되는 것이고 둘 중작은값을 취한다.
   2. 문자열 조각이 존재하지 않는다.
      1. 고려할 필요가 없다.

시간복잡도

N = 20,000 길이의 문자열을 1부터 확인한다.

size만 고려한다 (최대 5개)