[슬라이딩 윈도우] DNA 비밀번호 / 백준 12891

슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위를 유지한채로 이동하며 문제를 해결합니다.

투포인터 알고리즘과 매우비슷하고 원리도 간단합니다. 투포인터와 마찬가지로 슬라이딩 윈도우 알고리즘도 

O( n )의 시간복잡도 알고리즘입니다.

 

아래는 슬라이딩 윈도우 문제와 풀이입니다.

 

 

문제

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

 

 

 

 

 

풀이

임의로 만든 DNA가 GATA이고 비밀번호로 사용될 문자열의 길이가 2, 포함되어야할 ACGT 최소갯수는 1001 일경우 아래와 같습니다.

 

첫번째 윈도우는 GA이기 때문에 현재상태 배열에 A와 G에 해당하는 인덱스에 숫자 1을 넣어줍니다.

그리고 현재상태 배열과 비밀번호 조건 배열을 비교합니다. 비밀번호 조건은 A와 T가 최소한 한개는 포함되어 있어야 가능한데 T가 0개 이므로 GA의 비밀번호 문자열은 비밀번호로 사용이 불가 하기 때문에 카운트 되지 않습니다.

 

 

그 다음 문자열을 확인 하기 위해 오른쪽으로 한칸 이동합니다. 한칸 이동되면서 왼쪽의 G가 빠지고 T가 추가 되기 때문에 왼쪽값을 현재상태 배열에서 빼주고 오른쪽 값을 현재상태 배열에 추가 해주어 G는 1에서 0이 되고 T는 0에서 1이 됩니다. 한칸씩 이동되며 체크를 하기 때문에 왼쪽값 제거, 오른쪽값 추가로 두 데이터만 수정해주면 됩니다.

 

이상태로 현재상태 배열과 비밀번호 조건 배열을 비교 해보겠습니다. 비밀번호 조건인 AT가 현재상태 배열에도 한개씩 가지고 있기 때문에 AT문자열은 비밀번호로 사용이 가능하므로 숫자를 카운팅 해주면 됩니다. 이와 같은 방식으로 한칸씩 이동해서 확인하여 비밀번호로 사용이 가능한 경우의 수를 출력 합니다.

 

 

import java.io.*

// 슬라이딩 윈도우 기법을 사용

var conditionArr = IntArray(4)
var checkCnt = 0    // checkCnt가 4가 되면 (각자리 조건4개가 충족되면) result +1
fun main(args: Array<String>) {

    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))

    // 결과값 변수
    var result = 0

    // s : 임의로 만든 DNA 문자열 길이 s
    // p : 비밀번호로 사용할 부분문자열의 길이 p
    var (s,p) = br.readLine().split(" ").map { it.toInt() }

    // dna : 임의로 만든 dna 문자열
    var dna = br.readLine()

    // c : 부분문자열에 포함되어야 할 {‘A’, ‘C’, ‘G’, ‘T’} 의 최소 개수
    var c = br.readLine().split(" ").map { it.toInt() }

    // dnaArr : 현재 상태배열
    var dnaArr = IntArray(4) { 0 }

    // conditionArr : 비밀번호 조건
    conditionArr = IntArray(4) { 0 }

    for (i in c.indices) {  // 0 until c.size
        conditionArr[i] = c[i]
        if (c[i] == 0) checkCnt++   // 0개라는건 없어도 된다는거니까 무조건 조건충족이라 checkCnt를 +1
    }

    // 부분문자열 길이 만큼의 dna배열 만들기
    for (i in 0 until p) {
        dnaArr = addDna(dna[i], dnaArr)
    }

    if (checkCnt == 4) result++

    // n : 슬라이딩 하는 횟수
    var n = s-p
    var tmpDnaArr = dnaArr

    // p(부분문자열길이)에서 s(임의로만든dna길이)까지 하기 때문에 부분 문자열을 만들수 있는 횟수 만큼만 반복됨
    // 부분문자열이 한칸씩 오른쪽으로 이동하기 때문에 이동 할때마다 왼쪽(start)의 문자는 빼주고 오른쪽(end)의 문자는 추가 해주면서 왼쪽 오른쪽 문자만 갯수를 갱신해준다
    for (end in p until  s) {
        var start = end - p
        tmpDnaArr = removeDna(dna[start], tmpDnaArr)
        tmpDnaArr = addDna(dna[end], tmpDnaArr)
        if (checkCnt == 4) result++
    }

    bw.write(result.toString())
    bw.flush()
    bw.close()
}

fun addDna(s: Char, dnaArr: IntArray): IntArray {
    var tmpDnaArr = dnaArr
    if (s == 'A') {
        tmpDnaArr[0]++
        if (tmpDnaArr[0] == conditionArr[0]) checkCnt++     // 충족된 순간 한번만 +1해준다. 조건문을 >= 이렇게 해놓으면 한자리에 checkCnt가 여러번 증가 될수 있다.
    } else if (s == 'C') {
        tmpDnaArr[1]++
        if (tmpDnaArr[1] == conditionArr[1]) checkCnt++
    } else if (s == 'G') {
        tmpDnaArr[2]++
        if (tmpDnaArr[2] == conditionArr[2]) checkCnt++
    } else if (s == 'T') {
        tmpDnaArr[3]++
        if (tmpDnaArr[3] == conditionArr[3]) checkCnt++
    }

    return tmpDnaArr
}
fun removeDna(s: Char, dnaArr: IntArray): IntArray {
    var tmpDnaArr = dnaArr
    if (s == 'A') {
        if (tmpDnaArr[0] == conditionArr[0]) checkCnt--     // 지금은 같지만 다음 라인에서 -- 되기 때문에 충족값보다 적어지기 때문에 checkCnt를 -1 해준다.
        tmpDnaArr[0]--
    } else if (s == 'C') {
        if (tmpDnaArr[1] == conditionArr[1]) checkCnt--
        tmpDnaArr[1]--
    } else if (s == 'G') {
        if (tmpDnaArr[2] == conditionArr[2]) checkCnt--
        tmpDnaArr[2]--
    } else if (s == 'T') {
        if (tmpDnaArr[3] == conditionArr[3]) checkCnt--
        tmpDnaArr[3]--
    }
    return tmpDnaArr
}