[LeetCode] 2466. Count Ways To Build Good Strings

https://leetcode.com/problems/count-ways-to-build-good-strings/description/

---

문제

 

Given the integers zero, one, low, and high, we can construct a string by starting with an empty string, and then at each step perform either of the following:

• Append the character '0' zero times.
• Append the character '1' one times.

This can be performed any number of times.

A good string is a string constructed by the above process having a length between low and high (inclusive).

Return the number of different good strings that can be constructed satisfying these properties. Since the answer can be large, return it modulo 10^9 + 7.

 

Example 1:

Input: low = 3, high = 3, zero = 1, one = 1
Output: 8
Explanation: 
One possible valid good string is "011". 
It can be constructed as follows: "" -> "0" -> "01" -> "011". 
All binary strings from "000" to "111" are good strings in this example.

Example 2:

Input: low = 2, high = 3, zero = 1, one = 2
Output: 5
Explanation: The good strings are "00", "11", "000", "110", and "011".

 

Constraints:

• 1 <= low <= high <= 105
• 1 <= zero, one <= low

---

풀이

풀이 과정

zero, one, low, high 4개의 정수 변수가 주어진다. 

아래 두 개의 조건에 따라 문자열을 만들어 나간다.

• '0'을 zero번 붙인다.
• '1'을 one번 붙인다.

이렇게 만들 수 있는 문자열 중 문자열의 길이가 low이상 high이하인 문자열을 good string으로 정의하며 good string의 총 개수를 구하는 문제이다.

정답이 매우 큰 수 일 수 있으므로 10^9 + 7로 나눈 나머지를 return한다.

 

dp를 이용하여 각 자리수마다 만들 수 있는 문자열의 경우의 수를 구하고 그 길이가 low이상 high이하인 경우의 수를 더한 값을 return하는 방식으로 풀이한다.

각 자리수마다 만들어질 수 있는 경우의 수를 저장할 배열을 선언하고 첫 번째값을 1로 세팅한다.

// 각 자리수마다 만들어질 수 있는 경우의 수를 저장할 배열
int[] dp = new int[high + 1];
// 아무것도 만들수 없는 경우의 수 1
dp[0] = 1;

 

단어를 만들 수 있는 최소한의 길이는 zero와 one중 작은 값이다. 단어를 만들 수 있는 최소한의 길이보다 작은 경우에는 만들 수 있는 경우의 수가 존재하지 않으므로 이 최소 길이부터 탐색을 시작한다.

현재 탐색중인 문자열 자리수가 0이 들어갈 개수 이상인 경우 zero만큼 이전 자리수의 경우의 수 만큼의 개수를 현재 인덱스 값에 추가한다.
1이 들어갈 경우에 대해서도 같은 방법으로 탐색한다.

만약 현재 탐색중인 문자열 자리수가 good string이 되는 길이인 경우에는 정답에 현재 인덱스의 값을 추가한다.
모든 탐색이 종료된 후 최종적으로 구해진 정답을 return한다.

int answer = 0;
// 단어를 만들 수 있는 최소 길이
int minLength = Math.min(zero, one);
// 나머지 계산을 위한 수
int mod = 1000000007;

// 단어를 만들 수 있는 최소 길이부터 탐색
for(int i = minLength; i <= high; i++) {
    // 현재 탐색중인 문자열 자리수가 0이 들어갈 개수 이상인 경우
    if(i >= zero) {
        // 0의 개수 이전 자리수의 경우의 수 만큼 추가
        dp[i] = (dp[i] + dp[i - zero]) % mod;
    }
    // 현재 탐색중인 문자열 자리수가 1이 들어갈 개수 이상인 경우
    if(i >= one) {
        // 1의 개수 이전 자리수의 경우의 수 만큼 추가
        dp[i] = (dp[i] + dp[i - one]) % mod;
    }
    // 현재 탐색중인 문자열 자리수가 good string이 되는 길이인 경우
    if(i >= low) {
        // 정답 개수 추가
        answer = (answer + dp[i]) % mod;
    }
}

return answer;

 

---

최종 코드

class Solution {
    public int countGoodStrings(int low, int high, int zero, int one) {
        int answer = 0;
        
        // 단어를 만들 수 있는 최소 길이
        int minLength = Math.min(zero, one);
        // 나머지 계산을 위한 수
        int mod = 1000000007;
        // 각 자리수마다 만들어질 수 있는 경우의 수를 저장할 배열
        int[] dp = new int[high + 1];
        // 아무것도 만들수 없는 경우의 수 1
        dp[0] = 1;
        
        // 단어를 만들 수 있는 최소 길이부터 탐색
        for(int i = minLength; i <= high; i++) {
            // 현재 탐색중인 문자열 자리수가 0이 들어갈 개수 이상인 경우
            if(i >= zero) {
                // 0의 개수 이전 자리수의 경우의 수 만큼 추가
                dp[i] = (dp[i] + dp[i - zero]) % mod;
            }
            // 현재 탐색중인 문자열 자리수가 1이 들어갈 개수 이상인 경우
            if(i >= one) {
                // 1의 개수 이전 자리수의 경우의 수 만큼 추가
                dp[i] = (dp[i] + dp[i - one]) % mod;
            }
            // 현재 탐색중인 문자열 자리수가 good string이 되는 길이인 경우
            if(i >= low) {
                // 정답 개수 추가
                answer = (answer + dp[i]) % mod;
            }
        }

        return answer;
    }
}

---