Leetcode 995. Minimum Number of K Consecutive Bit Flips

문제

You are given a binary array nums and an integer k.

A k-bit flip is choosing a subarray of length k from nums 
and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of k-bit flips required so that 
there is no 0 in the array. If it is not possible, return -1.

A subarray is a contiguous part of an array.

이진 배열 nums와 정수 k가 주어진다.
사용자는 이진 배열에서 k 길이 만큼의 부분 배열 부분을 비트플립 할수 있다.

• 즉, 연속된 k길이만큼 0은 1로 1은 0으로 변경한다.

이 연산을 n번 했을때 모든 배열의 값을 1로 변경할수 있다면 최소한으로 드는 연산의 횟수를 구하시오.

예시

• nums가 [0, 0, 0, 1, 0, 1, 1, 0] 이고 k가 3일때
  

1. 0~2 index를 비트플립
   
2. 4~6 index를 비트플립
   
3. 5~7 index를 비트플립
   

• 총 3번 flip으로 해결할수 있다.

제한

• $1 <= nums.length <= 10^5$
• $1 <= k <= nums.length$

알아 둘 것

• 이 문제가 엄청 복잡해 보이지만 사실 푸는 방법 자체는 정해져 있다!
• 왼쪽부터 loop를 돌리면서 0이 나오면 그부분부터 k길이만큼 flip하면 풀이가 가능하다는 전제 하에 무조건 풀린다!
• 예시도 보면 왼쪽에서 오른쪽으로 이어나가는것을 알수 있다.

그러면 뭐가 문제일까

• flip을 직접 하면 n^2 시간복잡도여서 너무 오래 걸린다.
• deque를 이용해 자신의 index에 영향을 미치는 flip의 갯수를 카운팅 해 구할수 있다!

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        q = collections.deque()

        ans = 0

        N = len(nums)

        for right in range(N):
        	# 더이상 자신의 index에 영향을 미치지 않는 flip은 제거한다.
            while q and q[0] <= right - k:
                q.popleft()
            # 더이상 flip을 진행할수 없는 길이인데 0이 나오면 완성될수 없다.
            if N - k < right and (nums[right] + len(q)) % 2 == 0:
                return -1
            # flip을 진행하고 시작 index를 queue 에 기록한다.
            if (nums[right] + len(q)) % 2 == 0:
                ans += 1
                q.append(right)

        return ans

게임 코드

import pygame
import sys

# Initialize Pygame
pygame.init()

# Constants
WIDTH, HEIGHT = 800, 600
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
GREEN = (0, 255, 0)
RED = (255, 0, 0)
FONT_SIZE = 40

# Screen setup
screen = pygame.display.set_mode((WIDTH, HEIGHT))
pygame.display.set_caption("K-bit Flip Game")
font = pygame.font.Font(None, FONT_SIZE)

# Game variables
k = 3
nums = [0,0,0,1,0,1,1,0]
cell_size = WIDTH // len(nums)
flips = 0

def draw_array():
    for i, num in enumerate(nums):
        color = GREEN if num == 1 else RED
        pygame.draw.rect(screen, color, pygame.Rect(i * cell_size, HEIGHT // 2 - cell_size // 2, cell_size, cell_size))
        text = font.render(str(num), True, WHITE)
        screen.blit(text, (i * cell_size + cell_size // 2 - FONT_SIZE // 4, HEIGHT // 2 - FONT_SIZE // 2))

def flip_subarray(start):
    global flips
    if start + k > len(nums):
        return
    for i in range(start, start + k):
        nums[i] = 1 - nums[i]
    flips += 1

def check_win():
    return all(num == 1 for num in nums)

# Game loop
running = True
while running:
    screen.fill(BLACK)
    draw_array()
    win = check_win()
    
    if win:
        win_text = font.render("You Win!", True, WHITE)
        screen.blit(win_text, (WIDTH // 2 - FONT_SIZE, HEIGHT // 4))
    
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
        elif event.type == pygame.MOUSEBUTTONDOWN and not win:
            x, y = event.pos
            if HEIGHT // 2 - cell_size // 2 <= y <= HEIGHT // 2 + cell_size // 2:
                index = x // cell_size
                flip_subarray(index)
    
    pygame.display.flip()

pygame.quit()
sys.exit()

• pygame을 설치하시고 nums와 k를 설정해 직접 해보실수 있습니다.