[Swift 백준] 14465 소가 길을 건너간 이유 5

슬라이딩 윈도우 란

• 슬라이딩 윈도우(Sliding Window)는 연속된 구간을 다루는 문제에서 효율적인 계산을 위한 기법입니다. 주로 배열이나 문자열에서 연속된 구간을 처리할 때 사용됩니다. 이 기법은 한 번 계산한 값을 재사용하여 중복 작업을 줄이고, 전체 시간 복잡도를 최적화합니다.
• 슬라이딩 윈도우는 두 개의 포인터(혹은 인덱스)를 사용하여 연속된 구간을 탐색하는 방식입니다.
• 왼쪽 포인터(left)와 오른쪽 포인터(right)가 배열을 따라 이동하며 구간을 탐색합니다.
  처음에는 구간을 정하고, 이후 포인터를 이동시키면서 구간의 상태를 업데이트합니다.
  중요한 점은 구간의 시작과 끝만 변경하여 전체 배열을 다시 탐색하지 않고 효율적으로 계산한다는 것입니다.

풀이 아이디어

• 불이 꺼져있는 구간을 구한다
• 최초 부족한 신호등의 개수를 '기억' 하여 재사용한다
• 구간을 옮겨가며 최소값으로 대치하여 결과값을 도출한다

풀이

// 총길이: n, 원하는 길이: k, 고장난거: b

let nkb = readLine()!.split(separator: " ").map { Int($0)! }
let (n, k, b) = (nkb[0], nkb[1], nkb[2])

// 우선 전부 켜진걸로 초기화
var lightArr = Array(repeating: 1, count: n)

// 입력받은값은 0으로 꺼짐을 표시
for _ in 0..<b {
    let input = Int(readLine()!)!
    lightArr[input - 1] = 0
}

var left = 0
var count = 0

// 최초 고장난 개수를 구합니다
for i in 0..<k {
    if lightArr[i] == 0 {
        count += 1
    }
}

// result를 갱신 할 예정
var result = count

for i in k..<n {
    if lightArr[i] == 0 {
        count += 1
    }
    if lightArr[left] == 0 {
        count -= 1
    }
    left += 1
    // 최소값으로 갱신
    result = min(result, count)
}

print(result)