Leetcode 3753. Total Waviness of Numbers in Range II

문제

You are given two integers num1 and num2 representing an inclusive range [num1, num2].

The waviness of a number is defined as the total count of its peaks and valleys:

A digit is a peak if it is strictly greater than both of its immediate neighbors.
A digit is a valley if it is strictly less than both of its immediate neighbors.
The first and last digits of a number cannot be peaks or valleys.
Any number with fewer than 3 digits has a waviness of 0.
Return the total sum of waviness for all numbers in the range [num1, num2].

두 정수 num1과 num2가 주어지며, 이는 포함 범위 [num1, num2]를 나타냅니다.

숫자의 waviness는 그 숫자 안에 있는 peak와 valley의 총 개수로 정의됩니다.

어떤 자릿수가 peak가 되려면, 그 자릿수가 양쪽에 바로 인접한 두 자릿수보다 엄격하게 커야 합니다.

어떤 자릿수가 valley가 되려면, 그 자릿수가 양쪽에 바로 인접한 두 자릿수보다 엄격하게 작아야 합니다.

숫자의 첫 번째 자릿수와 마지막 자릿수는 peak나 valley가 될 수 없습니다.

자릿수가 3개보다 적은 숫자의 waviness는 0입니다.

범위 [num1, num2] 안에 있는 모든 숫자들의 waviness 총합을 반환하세요.

예시

Input: num1 = 120, num2 = 130

120과 130 사이의 waviness가 있는 숫자는

120, 121, 130 총 3개이다.

제한

$1 <= num1 <= num2 <= 10^{15}$

풀이

1. num1~num2 까지의 waviness의 총 합은 곧

• 0 ~ num2까지의 총합에 0 ~ num1 - 1을 한것과 정확하게 동일하다.

2. 각 digit을 dp로 보아 계산한다.

class Solution:
    def totalWaviness(self, num1: int, num2: int) -> int:
        def finder(n: int) -> int:
            if n < 100:
                return 0

            digits = [int(c) for c in str(n)]

            @cache
            def dp(pos: int, prev2: int, prev1: int, length: int, tight: int) -> Tuple[int, int]:
                if pos == len(digits):
                    return 1, 0

                limit = digits[pos] if tight else 9

                tot_cnt = 0
                tot_wav = 0

                for d in range(limit + 1):
                    ntight = tight and digits[pos] == d

                    if length == 0 and d == 0:
                        cnt, wav = dp(pos + 1, -1, -1, length, ntight)
                        tot_cnt += cnt
                        tot_wav += wav
                        continue

                    if length == 0:
                        cnt, wav = dp(pos + 1, -1, d, length + 1, ntight)
                        tot_cnt += cnt
                        tot_wav += wav
                        continue

                    if length == 1:
                        cnt, wav = dp(pos + 1, prev1, d, length + 1, ntight)
                        tot_cnt += cnt
                        tot_wav += wav
                        continue

                    add = 0

                    if prev2 > prev1 < d:
                        add = 1
                    elif prev2 < prev1 > d:
                        add = 1

                    cnt, wav = dp(pos + 1, prev1, d, length + 1, ntight)

                    tot_cnt += cnt
                    tot_wav += wav + add * cnt

                return tot_cnt, tot_wav

            return dp(0, -1, -1, 0, True)[1]

        return finder(num2) - finder(num1 - 1)