[LeetCode] 413. Arithmetic Slices - 구현(DFS) JAVA

https://leetcode.com/problems/arithmetic-slices/description/?envType=problem-list-v2&envId=dynamic-programming

코드설명

동적계획법(Dynamic Programming) + 구현(DFS) 을 활용합니다.

 

처음에 정답을 작성했을때의 방식은 다음과 같습니다.

[1, 3, 5, 7, 9, 10, 13, 16] 이 존재한다고 해봅시다.

각 구간의 차이는 [2, 2, 2, 2, 1, 3, 3] 입니다.

이때, [0...4]에 대하여 등차수열임을 알 수 있습니다. 그러면,

(1, 3, 5) (1, 3, 5, 7) (1, 3, 5, 7, 9)

(3, 5, 7) (3, 5, 7, 9)

(5, 7, 9)

가 모든 경우의 수입니다. 어떤 규칙이 보이시나요?

네. 3 + 2 + 1 로 처리했니다. 즉 (right - left - 2 ) 에 대하여 1이 될떄까지 시그마 연산을 하면 됩니다.

 

더 간단한 방식이 있을까 싶어, 다른 분들의 코드를 살펴보았습니다. 2번쨰 방식으로 넘어갑니다.

문제에서 요구하는 바는 최소 3개의 등차수열을 원합니다. 그렇기에 

nums[i] - nums[i-1] == nums[i-1] - nums[i-2]가 성립하는지 확인하고,  current값을 누적시켜가며 count값에 계속해서 더해나갑니다.

위와 같은 예제로 다시 살펴보겠습니다.

[1, 3, 5] 성공  -> [3, 5, 7] 성공 했을떄 [1, 3, 5, 7] 도 성공한것과 마찬가지입니다. 

그러므로 current++ 한뒤 count값에 그대로 더해줍니다.

코드

정답코드2입니다.

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if(nums.length < 3) return 0;

        int count = 0;
        int current = 0;

        for(int i=2; i<nums.length; i++){
            if(nums[i] - nums[i-1] == nums[i-1] - nums[i-2]){
                current++;
                count += current;
            }else {
                current = 0;
            }
        }
        return count;
    }

}

 

정답코드1입니다.

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if(nums.length < 3) return 0;
        Arrays.fill(cache, -1);
        for(int i=0; i<nums.length; i++){
            nums[i] += 1000;
        }
        int answer = 0;
        int left = 0;
        int right = 1;
        int sDiff = nums[right] - nums[right - 1];
        while(right < nums.length){
            int nDiff = nums[right] - nums[right - 1];

            if(nDiff == sDiff){
                right++;
            }else if(nDiff != sDiff){
                sDiff = nDiff;
                if(right - left >= 3){
                    if(right - left - 2 >= 0){
                        answer += sumFunc(right - left - 2);
                    }
                }
                left = right - 1;
                right = right;
            }
        }
        
        if(right - left + 1 >= 3){
            if(right - left - 2 >= 0 ){
                answer += sumFunc(right - left - 2);
            }
        }
        return answer;
    }

    int[] cache = new int[5001];
    int sumFunc(int num){
        if(num == 0) return 0;
        if(cache[num] != -1) return cache[num];
        return cache[num] = sumFunc(num - 1) + num;
    }

}