[leetcode] 1493. Longest Subarray of 1's After Deleting One Element 파이썬 코드

https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element

 

배열이 있을 때 반드시 한 원소를 지워야 한다. 0을 하나 지웠을 때 연속된 1을 가지는 가장 긴 subarray의 길이를 구하라.

 

예를 들어, nums = [1, 1, 0, 1] 이런 배열이 있다고 할 때 2번째 인덱스의 0을 지워버리면 길이가 3인 [1, 1, 1]이라는 subarray를 만들 수 있다. 그러므로 답은 3이다. 

 

내가 생각한 방법은 0이 아닌 연속된 1이 섬(island)처럼 느껴졌다. bfs 문제풀 때 독립된 섬의 개수를 구하는 문제가 오버랩되었다.

 

그래서 연속된 1은 더하고, 0은 -1로 처리해줬다. 즉, nums 배열을 [2, -1, 1] 이런 식으로 만들었다.

그런 다음에 저 -1을 기준으로 왼쪽과 오른쪽을 더했을 때 최댓값이 나오는지 확인했다. 

 

nums = [0, 1, 1, 1, 0, 1, 1, 0, 1] 일 때, numsChanged = [-1, 3, -1, 2, -1, 1] 이다.

그러면 -1이 3번 등장하는데 첫 번째 -1은 확인하지 않는다.

2번째와 3번째 -1을 확인하는데 2번째 -1에서 왼쪽과 오른쪽을 더하면 5이고,

3번째 -1에서 왼쪽과 오른쪽을 더하면 3이므로

답은 5가 된다.

 

class Solution(object):
    def longestSubarray(self, nums):
        numsChanged = []
        temp = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                if temp > 0:
                    numsChanged.append(temp)
                    temp = 0
                numsChanged.append(-1)
            else:
                temp += 1
        if temp > 0:
            numsChanged.append(temp)

        result = 0

        if sum(numsChanged) == len(numsChanged) * (-1): # 모든 배열의 원소가 0이라는 얘기!
            return 0
        elif -1 not in numsChanged: # nums 배열에 0이 없다면 len(nums)에서 1을 빼주면 된다!
            return len(nums)-1
        else:
            for i in range(len(numsChanged)):
                if numsChanged[i] >= 1:
                    result = max(result, numsChanged[i])
                else:
                    if i - 1 >= 0 and i + 1 < len(numsChanged):
                        result = max(result, numsChanged[i-1] + numsChanged[i+1])

            return result