1416. Restore The Array / TypeScript

A program was supposed to print an array of integers. The program forgot to print whitespaces and the array is printed as a string of digits s and all we know is that all integers in the array were in the range [1, k] and there are no leading zeros in the array.

Given the string s and the integer k, return the number of the possible arrays that can be printed as s using the mentioned program. Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

Example 2:

Input: s = "1000", k = 10
Output: 0
Explanation: There cannot be an array that was printed this way and has all integer >= 1 and <= 10.

Example 3:

Input: s = "1317", k = 2000
Output: 8
Explanation: Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]

 

출처 : https://leetcode.com/problems/restore-the-array/description/

 

풀이

 

const MODULUS = (10 ** 9) + 7 

function numberOfArrays(s: string, k: number): number {
    const memo:number[] = [] // 메모이제이션 배열
    const dp = (index:number):number => {
        if(index == s.length) return 1 // 문자열 끝까지 나누었을 때
        if(s[index] == '0') return 0 // 0으로 시작하는 경우
        if(memo[index] != undefined) return memo[index] // 이미 계산된 경우

        let ways = 0
        for(let i = index+1; i <= s.length; i++){ // 가능한 부분 문자열 탐색
            if(Number(s.substring(index, i)) <= k){ // 부분 문자열이 k 이하인지 확인
                ways += dp(i) // 가능한 경우의 수를 더함
            }else{
                break // k를 초과하면 중단
            }
        }
        memo[index] = ways % MODULUS // 결과를 MODULUS로 나눈 나머지 저장
        return memo[index] // 결과 반환
    }
    return dp(0) // dp 함수 호출
};

 

문자열 s를 주어진 정수 k를 기준으로 가능한 경우의 수만큼 나누는 방법을 찾는 문제

문제 설명

• 주어진 문자열 s는 숫자들로 이루어져 있음.
• k는 정수.
• 우리는 문자열 s를 여러 부분으로 나누되, 각 부분 문자열이 정수로 변환되었을 때 k보다 작거나 같아야 함.
• 각 부분 문자열은 0으로 시작하면 안 됨(즉, 앞에 0이 있으면 안됨).
• 이때 가능한 나누는 방법의 수를 계산하고, 그 값을 MODULUS = (10^9) + 7로 나눈 나머지를 반환.

풀이 과정

1. 동적 계획법(DP) 함수: dp(index)는 s[index:] 부분 문자열을 가능한 방법으로 나누는 경우의 수를 계산.
   • index == s.length인 경우: 문자열을 끝까지 다 나누었다는 의미이므로 가능한 경우의 수는 1.
   • s[index] == '0': 부분 문자열이 0으로 시작하는 경우는 불가능하므로 경우의 수는 0
   • 메모이제이션(memo[index]): 이미 계산한 경우의 수는 재사용.
2. 나누는 방법 탐색:
   • for 루프를 사용하여 index부터 문자열을 차례대로 나눔.
   • 부분 문자열 s[index:i]를 정수로 변환한 값이 k 이하인 경우에만 다음 단계로 나아. 그렇지 않으면 더 이상 나눌 수 없으므로 반복문을 중단.
   • dp(i)는 s[i:]를 나누는 경우의 수를 반환하며, 이를 누적하여 ways에 더
3. MOD 연산: 결과값은 매우 클 수 있으므로 MODULUS로 나눈 나머지를 저장하고 반환

 

예시 s = "1000", k = 10000

1. 기본 조건 설정

먼저 MODULUS = 10^9 + 7은 결과가 너무 커질 때 이를 제한하기 위해 도입된 값

2. 초기 상태 및 함수 호출

입력된 문자열은 "1000"이며, 처음에 numberOfArrays("1000", 10000)이 호출.

이 함수는 내부에서 동적 계획법 함수 dp(0)을 호출

• dp(0)은 문자열 s[0:] = "1000"을 어떻게 나눌 수 있을지 탐색

3. dp(0) 계산 과정

3.1 첫 번째 반복: i = 1

• 먼저 부분 문자열 s[0:1] = "1"을 추출합니다.
• 이 값은 1, 즉 k = 10000보다 작으므로 유효한 나눔.
• 그러므로 dp(1)을 호출.

3.2 dp(1) 계산 과정

dp(1)

첫 번째 문자 s[1] = '0'이므로, 규칙상 0으로 시작하는 부분 문자열은 나눌 수 없음.
따라서 dp(1)은 0을 반환

3.3 dp(0)로 돌아와서

• dp(1)이 0을 반환했으므로, dp(0)은 이 부분에서 경우의 수를 얻지 못함
• 그러나 dp(0)은 계속해서 다른 부분 문자열을 탐색.

3.4 두 번째 반복: i = 2

• 다음으로 부분 문자열 s[0:2] = "10"을 추출.
• 10은 여전히 k = 10000보다 작으므로 유효
• dp(2)를 호출

3.5 dp(2) 계산 과정

dp(2)첫 번째 문자 s[2] = '0'이므로, 마

찬가지로 0으로 시작하는 부분 문자열은 유효하지 않음.

dp(2)도 0을 반환

3.6 dp(0)로 돌아와서

• dp(2)도 0을 반환했으므로, dp(0)은 여전히 유효한 나눔을 찾지 못.

3.7 세 번째 반복: i = 3

• 부분 문자열 s[0:3] = "100"을 추출
• 100은 k = 10000보다 작으므로 유효
• dp(3)를 호출

3.8 dp(3) 계산 과정

• 첫 번째 문자 s[3] = '0'이므로 0으로 시작하는 경우, 유효하지 않음. dp(3)도 0을 반환.

3.9 dp(0)로 돌아와서

• dp(3)이 0을 반환했으므로, 여전히 유효한 경우의 수를 찾지 못.

3.10 네 번째 반복: i = 4

• 부분 문자열 s[0:4] = "1000"을 추출
• 1000은 k = 10000보다 작으므로 유효
• dp(4)를 호출

3.11 dp(4) 계산 과정

• dp(4)은 s[4:]이 빈 문자열이 되었으므로, 문자열을 끝까지 다 나누었음을 의미.
• 이 경우는 유효한 나눔으로, 1을 반환합니다.

4. 결과 합산 및 반환

dp(0)은 마지막으로 유효한 나눔인 dp(4)에서 1을 받음 즉, 가능한 나누는 방법은 1가지

최종적으로, dp(0)에서 계산된 값은 1이며, 이를 MODULUS로 나눈 나머지를 반환하게 되므로 결과값은 1

전체 요약

• "1000"에서 나눌 수 있는 유효한 방법은 ["1000"] 한 가지 
• 따라서 결과값은 1