Arithmetic Slices

Arithmetic Slices

 

문제 내용

number array가 주어진다.

각 number의 연속적인 차가 동일할 경우 부분 집합의 갯수를 return해라

 

접근 방법

문제 내용을 보면 

[1,3,5,7,9]

[7,7,7,7]

[3,-1,-5,-9]

가 동일한 차를 갖고 있다고 한다.

예를 들어서 [7,7,7,7]은 [0,0,0]의 차를 동일하게 갖고 있다.

이 array는 left : [7,7,7] right : [7,7,7] 전체 [7,7,7,7] 이렇게 3개의 부분 집합을 만들 수 있다.

이 부분 집합의 갯수를 다음과 같이 추상화 해보자.

 

부분 집합 갯수 구하기

차의 집합을

[a,a]

라고 생각해 보자. 위에서 [7,7,7,7]은 [0,0,0]으로 구성되어 있음으로 이 동일 갑을 'a'라고 치환한 것이다.

• [a,a] : 1회
• [a,a,a] : [a,a],[a,a],[a,a,a] 3회 
• [a,a,a,a] : [a,a][a,a][a,a] , [a,a,a], [a,a,a] , [a,a,a,a] 7회
• [a,a,a,a,a] : [a,a][a,a][a,a][a,a] , [a,a,a], [a,a,a],[a,a,a]  , [a,a,a,a],[a,a,a,a], [a,a,a,a,a] 10회

가 된다.

패턴을 보면 a가 5개가 있을 때, [a,a]가 4번, [a,a,a]가 3번 [a,a,a,a]가 2번 [a,a,a,a,a]가 1번 나오는 것을 볼 수 있다.

$$ total = \frac{n(n-1)}{2} $$

의 형태로 표현할 수 있다.

이것을 dp의 형태로 바꾸면

[a,a] 동일 숫자가 나왔을 때 1회

[a,a,a] 동일 숫자가 나왔을 때 앞서 동일 숫자가 나온 dp의 값 + 1을 지금까지 나온 값이 더하는 형태로 표현 할 수 있다.

예를 들자면

1,2,3 사이의 차가 같고 최초 임으로 0 + 1 = 1을 dp에 넣는다.

다음은 dp[n-1]이 1임으로 1을 더해서 2 => 2+1은 3이 답이된다.

다음은 2에 1을 더해서 3을 더함으로 1+2+3 = 6이 답이된다.

마지막으로 4를 더함으로써 최종 결과인 10이 답으로 나온다.

 

프로그램

위의 형태를 아래와 같이 프로그램으로 표현할 수 있다.

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        if len(nums) < 2: return 0
        
        dp = [0] * len(nums)
        result = 0
        
        for idx in range(2, len(nums)):
            if nums[idx-2] - nums[idx-1] == nums[idx-1] - nums[idx]:
                dp[idx] = dp[idx-1] + 1
                result += dp[idx]
        
        return result

 

시간복잡도는 one pass임으로 $ O(N) $ 이 된다.