[CS] Sliding Window

서론

해당문제

"일정 횟수만큼 딛을 수 있는 돌 징검다리를 최대 몇 명이 넘어갈 수 있나"를 묻는 문제

시도

import kotlin.math.*

class Solution {
    fun solution(stones: IntArray, k: Int): Int {
        var answer = 0
        
        // println(stones.joinToString())
        var maxSpace = 0
        fun doCross() {
            var space = 0
            for(i in 0..stones.size-1) {
                stones[i]--
                if(stones[i] <= 0) {
                    space++
                    maxSpace = maxOf(maxSpace, space)
                } else {
                    space = 0
                }
            }
        }
        
        while(true) {
            doCross()
            answer++
            // println("--------------------------------")
            // println("$maxSpace : ${stones.joinToString()}")
            
            if(maxSpace >= k) break
        }
        
        return answer
    }

}

 직관적으로 풀었으나 복잡도를 살펴보면 O(n * 정답)이다. 최악의 경우 20만 x 20만이므로 효율 테스트에서 시간 초과로 실패했다.

 이 밖에도 효율적인 코드를 계속 고민하여 시도했지만 실패했고 힌트를 통해 Sliding Window 기법으로 해결할 수 있고 정리하려고 글을 쓴다.

Sliding Window의 아이디어

 일정 크기의 범위가 어떤 조건을 만족하는지 확인하기 위하여 사용하는 알고리즘이다. 시작과 끝을 나타내는 Two Pointer 기법을 사용하며 배열을 한 번만 돌기 때문에 O(n)의 복잡도를 가진다.

 정수형 배열에서 연속된 세 원소의 크기가 가장 큰 값을 찾는 문제를 생각해보자.

1. Window의 크기는 3이고 startIndex는 0, endIndex는 2이다.
2. answer 값을 arr[0] + arr[1] + arr[2]로 초기화한다.
3. while은 endIndex <= arr.lastIndex의 조건문을 가지고
4. sum = answer - arr[startIndex++] + arr[++endIndex]으로 정의한다.
5. answer = maxOf(answer, sum)으로 갱신한다.

위와 같이 사용할 수 있을 것이다.

문제에 적용하기

import java.util.ArrayDeque
import kotlin.math.*

class Solution {
    fun solution(stones: IntArray, k: Int): Int {
        val deque = ArrayDeque<Int>() // 인덱스를 저장
        var minOfMax = Int.MAX_VALUE

        for (i in stones.indices) {
            // 윈도우 범위에서 벗어난 인덱스 제거
            if (deque.isNotEmpty() && deque.first() <= i - k) {
                deque.removeFirst()
            }

            // 현재 값보다 작은 값들은 뒤에서 제거 (최대값 유지)
            while (deque.isNotEmpty() && stones[deque.last()] <= stones[i]) {
                deque.removeLast()
            }

            deque.addLast(i)

            // 윈도우가 k 크기 이상일 때만 결과 갱신
            if (i >= k - 1) {
                minOfMax = minOf(minOfMax, stones[deque.first()])
            }
        }

        return minOfMax
    }
}

핵심 요약

• 각 구간마다 그 구간의 최댓값을 구하고, 모든 최댓값 중 가장 작은 것이 정답
  ∵ 구간의 최대값이 건널 수 있는 최대 인원이고, 그 값이 최소여야 징검다리가 끊기지 않을 것이다.

• deque엔 인덱스를 넣고, 내림차순으로 유지하면 deque.first()로 최댓값을 바로 구할 수 있다.
  ∵ 윈도우 범위를 판별하고 같은 원소가 여러 개일 수 있을 것이다.

하지만 위 알고리즘도 시간초과난다. 적절한 것은 이분 탐색인 듯 싶다.