[2024] Day7. 446. Arithmetic Slices II - Subsequence

gunny·2024년 1월 7일

Arithmetic Slices II - Subsequence Arithmetic Slices II - Subsequence python leetcode Arithmetic Slices II - Subsequence

코딩테스트

목록 보기

320/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 7일 (일)
Leetcode daily problem

446. Arithmetic Slices II - Subsequence

https://leetcode.com/problems/arithmetic-slices-ii-subsequence/

Problem

정수 배열 nums가 주어지면 nums의 모든 산술 부분 수열의 수를 반환합니다.
숫자가 최소한 세 개의 요소로 구성되고 연속된 두 요소의 차이가 동일한 경우를 산술이다.

예를 들어, [1, 3, 5, 7, 9], [7, 7, 7, 7] 및 [3, -1, -5, -9]는 산술 시퀀스이고, [1, 1, 2, 5, 7]은 수열이 아니다.
배열의 하위 시퀀스는 배열의 일부 요소(아마도 없음)를 제거하여 형성할 수 있는 시퀀스이다.

Solution

Dynamic programming

등차 수열의 부분 수열 중에서 등차가 같은 쌍의 개수를 찾는 문제이다.
부분 수열은 원래 수열의 순서를 유지하며 선택된 원소들의 집합이다.
문제의 요구사항은 등차가 같은 쌍을 찾는 것이므로,
부분 수열의 길이가 2 이상이어야 한다.

예를 들어, [2, 4, 6, 8, 10]의 경우, 등차가 2인 모든 부분 수열은 [2, 4, 6], [4, 6, 8], [6, 8, 10]입니다. 이 중에서 [2, 4, 6]과 [6, 8, 10]은 등차가 같은 쌍이므로, 답은 2가 된다.

dp(i, d)를 i번째 원소에서 시작하고 등차가 d일 때 등차 수열의 길이라고 정의하면, dp(i, d)를 구하는 방법을 사용한다.

i 이전의 원소들을 확인해서 등차가 d인 등차 수열을 찾는다.
찾은 등차 수열의 개수를 누적하면서 dp(i, d)를 갱신한다.
이를 모든 i와 d에 대해 반복하면 등차가 같은 모든 쌍을 찾을 수 있다.
코드로 구현할 때에는 적절한 자료 구조를 사용하여 중복 계산을 피하며 dp를 갱신한다.

Code

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        cnt = 0
        dp = [defaultdict(int) for _ in range(n)]

        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]
                dp[i][diff] += 1

                if diff in dp[j]:
                    dp[i][diff] += dp[j][diff]
                    cnt += dp[j][diff]

        return cnt