Arithmetic Slices [leetcode]

문제

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

Arithmetic Slices - LeetCode

 

문제풀이

 

아... 풀었는데 소 뒷걸음 치다 벌레 잡은 격이 느낌이다.

 

부분배열(contiguous subsequence of the array) 이 등차수열을 만족하는지 확인하고 맞다면 개수를 +1 해주는 문제였다.

부분배열을 검증하는 방법은 해당 배열의 모든 숫자와 등차수열 합공식에 넣은 값이 같은지 보면 된다.

if( 부분배열의 모든 숫자 합 == {(부분배열 첫번째숫자 + 부분배열 마지막숫자) / 2} )

(처음에는 모든 부분배열을 돌렸었다 → 당연히 timeout)

 

또 하나 신기한 규칙이 있는데 부분배열의 길이만 알수있으면 해당 부분배열의 부분배열을 알수 있게 된다.

{1,2,3} → 1개( 부분배열의 길이가 3 일때)

{1,2,3,4} → 3개 (부분배열의 길이가 4일때)

{1,2,3,4,5} → 6개 (부분배열의 길이가 5일때)

• 1,2,3 / 1,2,3,4 / 1,2,3,4,5 / 2,3,4 / 2,3,4,5 / 3,4,5

부분배열의 길이가 n일때 → (n-2)(n-1) / 2 로 부분배열을 전부 순회하지 않더라도 개수를 한번에 알수있다.

 

코드

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        result = 0
        idx = 0
        for i in range(len(nums)-2):
            add_num = 3
            while True:
                end_idx = idx+add_num
                if end_idx > len(nums):
                    cal_num = add_num - 2 - 1
                    result += (cal_num+1)*cal_num/2
                    break
                    
                temp_nums = nums[idx:end_idx]
                # print(temp_nums)
                if sum(temp_nums) == (len(temp_nums) * (temp_nums[0]+temp_nums[-1]) / 2):
                    add_num+=1
                else:
                    cal_num = add_num - 2 - 1
                    result += (cal_num+1)*cal_num/2
                    # print(cal_num, result)
                    break
            idx = end_idx-2
            
        return int(result)

 

시간이 엄청 오래걸렸다...