[Algotithm] Sliding Window

오늘은 Sliding Window 에 대해 알아보도록 하겠습니다.

배열이나 문자열 같은 선형 데이터 구조에서 고정되거나 변화하는 크기의 윈도우를 이동시키며 데이터를 처리하는 기법입니다.

여기서 윈도우란 연속된 요소의 SubArray라고 할 수 있습니다.

해결해야 하는 문제에 따라 고정 슬라이딩 윈도우, 가변 슬라이딩 윈도우로 나뉠 수 있습니다.

고정 슬라이딩 윈도우

문제예시

https://www.acmicpc.net/problem/12891

평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. 
DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 
예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 
이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다.

하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 
임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다. 
그래서 민호는 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이여야 비밀번호로 사용할 수 있다는 규칙을 만들었다.

임의의 DNA문자열이 “AAACCTGCCAA” 이고 민호가 뽑을 부분문자열의 길이를 4라고 하자. 
그리고 부분문자열에 ‘A’ 는 1개 이상, ‘C’는 1개 이상, ‘G’는 1개 이상, ‘T’는 0개 이상이 등장해야 비밀번호로 사용할 수 있다고 하자. 
이때 “ACCT” 는 ‘G’ 가 1 개 이상 등장해야 한다는 조건을 만족하지 못해 비밀번호로 사용하지 못한다. 
하지만 “GCCA” 은 모든 조건을 만족하기 때문에 비밀번호로 사용할 수 있다.

민호가 만든 임의의 DNA 문자열과 비밀번호로 사용할 부분분자열의 길이, 
그리고 {‘A’, ‘C’, ‘G’, ‘T’} 가 각각 몇번 이상 등장해야 비밀번호로 사용할 수 있는지 순서대로 주어졌을 때 
민호가 만들 수 있는 비밀번호의 종류의 수를 구하는 프로그램을 작성하자. 
단 부분문자열이 등장하는 위치가 다르다면 부분문자열이 같다고 하더라도 다른 문자열로 취급한다.

[입력]
첫 번째 줄에 민호가 임의로 만든 DNA 문자열 길이 S와 비밀번호로 사용할 부분문자열의 길이 P가 주어진다. 
(1 ≤ P ≤ S ≤ 1,000,000)
두번 째 줄에는 민호가 임의로 만든 DNA 문자열이 주어진다.
세번 째 줄에는 부분문자열에 포함되어야 할 {‘A’, ‘C’, ‘G’, ‘T’} 의 최소 개수가 공백을 구분으로 주어진다.
각각의 수는 S보다 작거나 같은 음이 아닌 정수이며 총 합은 S보다 작거나 같음이 보장된다.

[출력]
첫 번째 줄에 민호가 만들 수 있는 비밀번호의 종류의 수를 출력해라.

접근법

문제가 다소 길기에 예제 입력으로 다시 이해해 봅시다.

9 8
CCTGGATTG
2 0 1 1

길이가 9인 문자열에서 구하고자 하는 문자열의 길이는 8이며,

그 안에 적어도 A는 2개, G는 1개, T는 1개가 들어가면 됩니다.

여기서 S 즉 구하고자하는 문자열의 길이가 고정 슬라이드 윈도우의 길이가 됩니다.

 

먼저 입력을 받습니다.

let ns = readLine()!.split(separator: " ").map { Int("\($0)")! }
let DNA = Array(readLine()!)
let acgt = readLine()!.split(separator: " ").map { Int("\($0)")! }
var count = [0, 0, 0, 0]
var index = ["A":0, "C":1, "G":2, "T":3]

문자열내의 문자를 쉽게 다루기 위해 배열로 만듭니다.

또한 각 문자의 개수를 저장하는 변수와 해당 변수에 쉽게 접근하기 위한 딕셔너리도 정의합니다.

 

길이가 8인 윈도우를 시각화하면 다음과 같습니다.

v------v   -> CCTGGATT
CCTGGATTG
 ^------^  -> CTGGATTG

 

첫번째 부분 문자열의 각 문자의 개수를 수집해봅시다.

for i in 0..<ns[1] {
    count[index["\(DNA[i])"]!] += 1
}

이제 수집한 카운트의 각 값들이 acgt의 각 값들보다 모두 크면 됩니다.

첫번째 부분 문자열의 값을 보면 다음과 같습니다.

CCTGGATT
[1,2,2,3]

A의 개수가 모자릅니다.

두번째 부분 문자열도 살펴봅시다.

CTGGATTG
[1,1,3,3]

역시 A이 개수가 모자릅니다.

 

여기까지의 로직을 코드로 작성해보면 아래와 같습니다.

var flag = true
for i in 0..<acgt.count {
    if acgt[i] > count[i] {
        flag = false
        break
    }
}
if flag {
    result += 1
}

하나라도 개수가 모자르다면 해당 문자열을 패스합니다.

 

여기서 생각해봐야할 점이 있습니다.

두번째 문자열을 구하는 과정에서 다시 첫 문자부터 C,T,G,G...를 셀 필요가 있을까요?

아닙니다.

이전 부분 문자열에서 앞에서 문자 하나를 빼고, 새로 들어오는 문자를 세면 됩니다.

이걸 코드로 표현하면 어떻게 될까요?

 

우선 반복할 범위를 생각해봅시다.

첫 부분 문자열에서 우리는 S-1 인덱스까지 이미 탐색을 완료했습니다.

따라서 그 전까지를 숫자를 세기만 하면 되겠습니다.

그리고 이후부터는 그전 문자열의 가장 첫번째 문자의 개수를 뺍니다.

for i in 0..<ns[0] {
    if i < ns[1] {
        count[index["\(DNA[i])"]!] += 1
    } else {
        count[index["\(DNA[i-ns[1]])"]!] -= 1
        count[index["\(DNA[i])"]!] += 1
    }
}

 

이제 문자의 개수를 세는 코드도 추가합니다.

단 문자열의 개수가 충분할 때만 셉니다.

for i in 0..<ns[0] {
    if i < ns[1] {
        count[index["\(DNA[i])"]!] += 1
    } else {
        count[index["\(DNA[i-ns[1]])"]!] -= 1
        count[index["\(DNA[i])"]!] += 1
    }
    if i >= ns[1] - 1 {
        var flag = true
        for j in 0..<acgt.count {
            if acgt[j] > count[j] {
                flag = false
                break
            }
        }
        if flag {
            result += 1
        }
    }
}

이렇듯 길이가 8일 윈도우를 이동시켜가며 풀어나가기 때문에

고정 슬라이드 윈도우 기법이 사용되었다고 할 수 있다.

최종 코드

let ns = readLine()!.split(separator: " ").map { Int("\($0)")! }
let DNA = Array(readLine()!)
let acgt = readLine()!.split(separator: " ").map { Int("\($0)")! }
var count = [0, 0, 0, 0]
var index = ["A":0, "C":1, "G":2, "T":3]
var result = 0

for i in 0..<ns[0] {
    if i < ns[1] {
        count[index["\(DNA[i])"]!] += 1
    } else {
        count[index["\(DNA[i-ns[1]])"]!] -= 1
        count[index["\(DNA[i])"]!] += 1
    }
    if i >= ns[1] - 1 {
        var flag = true
        for j in 0..<acgt.count {
            if acgt[j] > count[j] {
                flag = false
                break
            }
        }
        if flag {
            result += 1
        }
    }
}
print(result)

가변 슬라이딩 윈도우

문제예시

https://leetcode.com/problems/count-number-of-nice-subarrays

예시 문제로 개념을 알아봅시다.

Given an array of integers `nums` and an integer `k`. 
A continuous subarray is called nice if there are `k` odd numbers on it.
Return the number of nice sub-arrays.

Ko: 배열에서 홀수 숫자가 정확히 k개 포함된 부분 배열의 개수를 구해야 합니다.

[Example 1]
- Input: nums = [1,1,2,1,1], k = 3
- Output: 2
- Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

[Example 2]
- Input: nums = [2,4,6], k = 1
- Output: 0
- Explanation: There are no odd numbers in the array.

[Example 3]
- Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
- Output: 16

여기서는 가변 윈도우를 사용합니다.

접근법

가변 슬라이드는 부분 배열의 길이가 변화합니다.

var subarrays = 0   // 결과
var initial_gap = 0 // k개의 홀수를 포함하는 부분 배열의 크기
var qsize = 0       // 현재 윈도우에서 홀수의 개수
var start = 0       // 윈도우의 시작 포인터(부분 배열의 첫 인덱스)

이후 부분 배열의 끝 인덱스를 0부터 늘려가면서 개수를 찾습니다.

for end in 0..<nums.count {
    if nums[end] % 2 == 1 {
        qsize += 1
    }

동시에 끝 인덱스가 증가될 때마다 해당 숫자가 홀수라면 홀수의 개수를 증가시킨다.

 

그리고 홀수의 개수가 k개가 되었을 때

k개를 유지하면서 앞쪽 인덱스를 증가시키며 개수를 센다.

if qsize == k {
    initial_gap = 0
    while qsize == k {
        qsize -= nums[start] % 2
        initial_gap += 1
        start += 1
    }
}

기본적으로는 k개가 만족하는 윈도우(부분 배열)의 크기가 홀수의 위치에 따라 변화하기 때문에

가변 슬라이딩 윈도우 기법이 사용되었다고 할 수 있다.

 

최종코드

class Solution {
    func numberOfSubarrays(_ nums: [Int], _ k: Int) -> Int {
        var subarrays = 0
        var initial_gap = 0
        var qsize = 0
        var start = 0
        for end in 0..<nums.count {
            if nums[end] % 2 == 1 {
                qsize += 1
            }
            if qsize == k {
                initial_gap = 0
                while qsize == k {
                    qsize -= nums[start] % 2
                    initial_gap += 1
                    start += 1
                }
            }
            subarrays += initial_gap
        }
        return subarrays
    }
}

Reference

https://leetcode.com/problems/count-number-of-nice-subarrays/editorial/