[리트코드] Max Consecutive Ones III - Sliding Window 기법

 

▼ 문제 링크

Max Consecutive Ones III - LeetCode

 

0과 1로만 이루어진 배열과 숫자 k가 주어진다. 이때, k개 만큼 0을 1로 바꿀 수 있다. k는 0부터 배열의 개수까지 모두 가능하며, 0을 k개만큼 1로 바꿨을 때, 가장 긴 연속된 1의 개수를 구해야 한다.

 

Binary Tree를 사용한 사람도 있지만, 우리는 훨씬 쉽게 "Sliding Window" 기법을 사용해 답을 구할 수 있음

"Sliding Window" 기법이란, 단어 그대로 창문을 밀 듯이 배열의 부분 배열을 만들고 다음 칸으로 조금씩 밀면서 확인하는 기법으로 시간 복잡도가 O(n), 공간 복잡도가 O(1)이라는 큰 장점이 있음. 방식만 알면 그리 어렵지도 않고 코드도 간편하니, 기억해뒀다가 앞으로도 자주 써먹어야겠다.

 

Sliding Window 기법이란?

Sliding Window 기법으로 구한 부분 배열

[1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0] 이라는 배열이 있을 때, 숫자0 2개와 연속된 1로 이루어진 부분 배열을 생각해 보자.

1번 배열은 [0, 0, 1, 1, 1, 1]이고, 이후에도 조건을 만족하는(숫자0 2개와 연속된 1로 이루어진) 배열이 또 있는지 찾아보기 위해 미닫이 창문을 옆으로 미는 것처럼 네모칸을 한 칸 옆으로 밀어본다. 그러면 [0, 1, 1, 1, 1, 0] 로 이루어진 2번 배열을 찾을 수 있다.

이렇게 조건을 만족할 때까지 startIndex와 endIndex를 조절해가면서 답을 찾는 방법으로, 배열에서 아주 유용하다.

(참고 링크: https://leetcode.com/problems/max-consecutive-ones-iii/discuss/582112/Swift-Sliding-Window.)

 

 

# 풀이 1
Sliding Window 기법

import Foundation

class Solution {
    func longestOnes(_ nums: [Int], _ k: Int) -> Int {
        var start = 0
        var sumOne = 0
        var result = 0

        for end in 0..<nums.count {
            if nums[end] == 1 {
                sumOne += 1
            }
            
            // nums[start...end] 속 0의 개수가 k보다 클 때
            // nums[start...end] 속 원소의 개수 - 1의 개수(sumOne) = 0의 개수
            if (end - start + 1 - sumOne) > k {
                sumOne -= nums[start]
                start += 1
            }
                                // nums[start...end] 속 0을 모두 1로 바꿨다고 가정
                                // 정확히 따지면 nums[start-1...end-1]임
                                // end를 포함하면 0의 개수가 k보다 크고, 두번째 if문에서 start를 1 증가시켜줬기 때문
                                // 하지만 index를 구하는 게 아니라 1의 개수(즉 1의 총합)를 구하는 거라 상관 X
            result = max(result, (end - start + 1))
        }

        return result
    }
}swift

주석에도 달아놨지만, 사실 두번째 if문에서 이미 만들어진 부분 배열은 주어진 k의 개수보다 0이 더 많은 상태라서 정확한 답을 구하려면 for문 1단계 전 end와 start 값을 찾아야 올바른 start, end index를 얻을 수 있음

하지만 우리는 정확한 index값을 찾는게 아니라 어쨋든 그 안에 주어진 요소들의 개수를 구하면 되는 거라 둘을 빼주기만 해도 답을 구할 수 있음