leetcode : Find All Good Indices

https://leetcode.com/problems/find-all-good-indices/

포인터를 이동시키면서 앞뒤를 비교하면 연속적인 non-decreasing 혹은 non-increasing order 숫자 개수를 알 수 있다. (increasing이 아니라 non-decreasing이라고 표현한 이유는 같은 숫자도 포함하게 하기 위해서다)

내 아이디어는 이 포인터를 양옆에 두고 이동시키면서 조건을 만족하는 연속적인 숫자가 양측에 k개 이상 된다 싶으면 인덱스를 append하는거였다.

class Solution:
    def goodIndices(self, nums: List[int], k: int) -> List[int]:
        if len(nums) < 2 * k + 1:
            return []
        
        answer = []
        
        left = 0
        right = 0
        
        i = 1
        
        while i < k:
            if nums[i] <= nums[i-1]:
                left += 1
            else:
                left = 0
            i += 1
        
        j = i + 2
        while j < i + 1 + k:
            if nums[j] >= nums[j-1]:
                right += 1
            else:
                right = 0
            j += 1
        
        while j < len(nums):
            if left >= k-1 and right >= k-1:
                answer.append(i)
            
            if nums[i] <= nums[i-1]:
                left += 1
            else:
                left = 0
                
            if nums[j] >= nums[j-1]:
                right += 1
            else:
                right = 0
            
            i += 1
            j += 1
        else:
            if left >= k-1 and right >= k-1:
                answer.append(i)
            
        return answer

버그를 두번정도 살짝 내주고 풀었다.

 

시간복잡도 O(1), 공간복잡도 O(1)의 최상의 코드지만

영 지저분해서 실전 인터뷰용 코드로 쓰기 적합해보이지 않는다.

 

다른 사람들은 어떻게 풀었을까?

 

class Solution:
    def goodIndices(self, a: List[int], k: int) -> List[int]:
        n, ans= len(a) ,[]
        dp1 , dp2= [1]*(n+1), [1]*(n+1)
        for i in range(1,n):
            if a[i-1]>=a[i]:  dp1[i]= dp1[i-1]+1
        
        for i in range(n-2,-1,-1):
            if a[i]<=a[i+1]:  dp2[i]= dp2[i+1]+1
        
        for i in range(k,n-k):
            if dp1[i-1]>=k and dp2[i+1]>=k: ans+= [i]
        return ans

오 이렇게 푸는 방법도 있네?

근데 엣지케이스 땜에 살짝 까다롭다 이해하기가.

n+1 길이의 list를 선언했는데 음..왜지? 리스트의 인덱스는 0부터 n까지 있고.. 첫번째 iteration은 1부터 n-1까지, 두 번째 iteration은 n-2부터 0까지 돈다. 

n = 3, k =1이라면?

길이 4짜리 리스트가 만들어지고 첫 iteration이 1부터 2까지, 두번째 iteration이 1부터 0까지..

아! original list의 길이를 고려하면 n-2부터 시작하는게 맞다. 이해했으~!