99클럽 코테 스터디 26일차 TIL Leetcode Continuous Subarrays

문제

 

나의 접근

문제 요약 : 연속된 부분 배열들 중 부분 배열 내의 차이가 2보다 크지 않은 경우의 수를 모두 구하는 문제이다.

제한 사항을 보니 일일이 1개짜리 배열, 2개짜리 배열 이런식으로 세다보면 시간초과 나기 딱 좋아보여서 투포인터를 생각하고 풀었다.

1. 시작은 0에서 s,e 모두 시작하고, 부분배열의 최대, 최소값을 index와 값을 저장한다.

2. e를 오른쪽으로 한 칸씩 움직이며, 조건에 맞도록 최대한 배열을 넓혀본다. (최대, 최소는 계속 tracking해야한다)

3. 조건에 맞지않을 경우 최대한 넓혔으니, answer에 경우의수들을 더한다.

4. 다음 숫자를 넣어야하므로, s를 조건을 어기게 하는 최대값 또는 최소값의 위치 다음으로 이동시켜 다음 숫자가 포함되어도 조건을 만족시키게 한다. 그 사이에 있을지 모르는 최대, 최소값도 갱신해준다.

5. 다음 숫자를 넣고 시작하기 직전의 s,e 값을 통해서 두 부분배열의 중복되는 값들을 계산해서 빼준다.

6. 위 과정을 반복하고, e가 끝까지 도달 후 마지막에 더해지지 않은 부분배열의 경우의 수들을 더해준다.

 

나의 코드

class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        answer=0
        s,e=0,0
        maxi=[0,nums[0]]
        mini=[0,nums[0]]
        while e<len(nums):
            if abs(maxi[1]-nums[e])>2 or abs(mini[1]-nums[e])>2:
                answer+=(1+(e-s))*(e-s)//2
                if abs(maxi[1]-nums[e])>2:
                    s=maxi[0]+1
                elif abs(mini[1]-nums[e])>2:
                    s=mini[0]+1
                mini=[s,nums[s]]
                maxi=[s,nums[s]]
                for i in range(s,e):
                    if nums[i]>=maxi[1]:
                        maxi=[i,nums[i]]
                    if nums[i]<=mini[1]:
                        mini=[i,nums[i]]
                answer-=(1+(e-s))*(e-s)//2
            if nums[e]>=maxi[1]:
                maxi=[e,nums[e]]
            if nums[e]<=mini[1]:
                mini=[e,nums[e]]
            e+=1
        answer+=(1+(e-s))*(e-s)//2
        return answer