[LeetCode] 3191. Minimum Operations to Make Binary Array Elements Equal to One I (Python)

Problem

 

Solution

sliding window

 

연속된 3개 숫자를 뒤집어서 모두 1로 바꿀 수 있는 최소한의 횟수를 구하는 문제.

당연히 2중포문을 쓰면 시간초과가 발생한다.

n-2까지만 검사해서 nums[i] == 0 이면 i ~ i+2까지 비트연산으로 1, 0을 뒤집는다.

연산이 끝나면 answer+=1

비트연산 파이선으로 ^= 이더라? 괜히 if~else 구문으로 바꾸고있었네

 

마지막에 2개숫자가 0이면 연속된 3자리가 아니라 못바꾸므로 바로 리턴 -1

아니면 answer return

 

Code

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n - 2):
            if nums[i] == 0:
                nums[i + 1] ^= 1
                nums[i + 2] ^= 1
                ans += 1
        #마지막 2자리가 0이면 못바꿈
        if nums[-1] == 0 or nums[-2] == 0:
            return -1
        return ans

마지막에 또는 한줄로 이렇게 해도된다.

return res if nums[-1] == 1 and nums[-2] == 1 else -1

 

Complexity

Time Complexity

O(n) - 배열을 한 번 순회함

 

Space Complexity

O(1) - 입력 배열 외 추가 공간 사용 없음