413. Arithmetic Slices

#Array #DynamicProgramming

 

 

어떤 정수 배열이 세 개 이상의 원소로 구성되어 있고 그 세 원소에서 연속된 두 원소의 차이가 같으면

그 배열을 산술이라고 하자. (ex. [1,3,5,7,9], [7,7,7,7], [3,-1,-3,-5,-9])

nums 라는 정수 배열이 주어졌을 때, 산술인 하위 배열의 개수를 반환하라.

여기에서 하위 배열이란 배열에서 연속된 일부를 의미한다.

 

---

Trial 1 : Python3, 22/03/04

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
    	# 배열 길이가 3 미만이면 산술인 하위 배열은 없다
        if len(nums)<3:
            return 0
        
        arSbCount = []	# 산술 하위 배열의 길이를 저장하는 리스트
        count = 1
        # 산술 하위 배열의 길이 구하기
        for i in range(len(nums)-2):
            dff = nums[i+1] - nums[i]	
            if dff == (nums[i+2] - nums[i+1]):
                # 산술을 만족하고 첫번째에 위치할 때
                if count == 1:
                    count = count+2
                else:
                    count += 1
            # 산술이 끝났을 때
            else:
                if count >= 3:
                    arSbCount.append(count)
                count = 1

        # 반복문이 끝나는 시점의 count 판단 
        if count >= 3:
            arSbCount.append(count)
        
        # 산술인 하위 배열의 길이로 개수 구하기
        re = 0
        if len(arSbCount) == 0:
            return 0
        for c in arSbCount:
            n = c-2
            while(n>0):
                re = re + n
                n -= 1
        return re
        
        '''
        # 하위 배열의 개수 구하는 다른 방법
        if len(arSbCount) == 0:
            return 0
        for c in arSbCount:
            re = re + (c*(c+1)/2) - (2*c-1)
        return int(re)
        '''

풀이:

먼저 산술의 조건에 원소의 개수가 3 이상이어야 한다고 했으므로 총 배열 길이가 3 미만이면 0을 반환한다.

 

다음으로 산술을 만족하는 하위 배열이 배열 안에 여러 개 있을 수 있으므로 각 하위 배열의 길이를 저장할 수 있는 리스트를 선언하고 산술 하위 배열의 길이를 구한다.

산술을 만족하는 또 다른 조건이 연속한 두 원소의 차가 같아야 한다고 했으므로

반복문의 인덱스를 첫 번째라고 했을 때 첫 번째와 두 번째의 차와 두번째, 세번째의 차를 비교하고 산술을 만족하면 현재 기준으로 삼고 있는 원소가 산술 하위 배열의 몇 번째 원소인지를 파악해 원소 개수를 누적한다.

 

그러다 더 이상 배열이 산술을 만족하지 않으면, 누적한 원소의 개수가 3 이상을 만족할 때 선언했던 리스트에 추가하고 count 를 다시 1로 초기화한다. 반복문이 끝나면 마지막 경우는 count 에 대해 판단하지 못했으므로 따로 판단을 거쳐 리스트에 추가한다.

 

산술 하위 배열의 길이를 토대로 개수를 구한다.

하위 배열의 길이가 3이면 1개, 4이면 (2+1)개, 5이면 (3+2+1)개, n이면 ((n-2)+(n-3)+...+1)개인 규칙을 발견하여 이 규칙을 적용해 개수를 세었다. 단순하게 반복문을 이용하는 방법과 수식을 이용하는 방법이 있는데 수식은 하위 배열의 길이가 n일 경우 개수가 ((n-2)+(n-3)+...+1) 인 것을 통해 1부터 n까지의 합을 수식으로 구하고 (n+(n-1))(즉, 2n-1)만큼 빼주었다.

 

 

리뷰:

결과 제출을 할 때 성능이 할 때마다 다르게 나와서 보통 여러 번 제출하곤 하는데 이번에는 같은 코드임에도 그 편차가 좀 컸다. 최고 성능은 런타임 99.52%, 메모리 97.59% 였다.

작성한 코드가 긴 편이라 별로 좋지 않은 결과가 나올 거라고 예상했는데 생각보다 잘 나와서 놀랐다.

그래도 아직 코드가 완전히 마음에 드는 건 아니라 더 간편하게 풀 수 있었는지 다른 사람들의 코드를 참고해 볼 생각이다.