백준 12891 dna비밀번호, 슬라이딩 윈도우, 코틀린

문제

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

12891번: DNA 비밀번호

 

 

풀이

입력값이 아래와 같다고 가정 해봅시다

4 2

GATA

1 0 0 1

 

 

임의로 만든 dna 문자열 GATA에서 사용할 부분문자열의 길이는 2입니다. 아래 그림1 처럼 GA, AT, TA 를 검사 하면 됩니다. 1001의 값은 ACGT의 충족 갯수의 값으로 부분 문자열이 충족해야할 조건은 그림2 처럼 A문자 1개 포함, T문자 1개 포함입니다. 즉, A,T가 포함되는 부분 문자열의 갯수를 구하면 됩니다.

 

아래의 경우 AT, TA 부분문자열로 출력값은 2개가 됩니다.

 

지금 예로든 입력값은 부분 문자열이 2로 짧기 때문에 부분 문자열을 구하는것에 큰 태스크가 필요 하지 않습니다.

하지만 부분 문자열의 최대 크기는 1,000,000으로 입력값이 커진다면 문자열을 세팅하는것에 큰 태스크가 걸릴 것입니다.

 

여기서 효율적으로 부분 문자열을 구하는 법은 부분 문자열의 가장 왼쪽의 문자를 제거 하고 가장오른쪽의 인덱스+1의 값을 추가 하여 2가지 문자만 수정하고 수정한 부분문자열의 ACGT 갯수만 갱신해주면 됩니다.

 

첫 부분 문자열인 GA에 대한 ACGT의 갯수를 구하면 1010입니다. 여기서 충족 조건인 1001이 되지 않기 때문에 답에 포함되지 않습니다. 그다음으론 AT를 검사 해야 하기 때문에 부분 문자열을 G를 삭제 하고 1010에서 G에 해당하는 숫자를 -1 해줘 1000으로 갱신합니다. 그리고 T를 추가 하여 1000에서 T에 해당하는 숫자를 +1해줘 1001로 갱신합니다. 1001은 비밀번호 부분문자 충족 갯수를 충족하기 때문에 출력값에 포합시킵니다. 

 

즉, 부분 문자열의 크기는 유지 하면서 한칸씩 오른쪽으로 이동한다고 생각 하면 됩니다.

이것을 슬라이딩 윈도우라고 합니다.

 

아래는 코드입니다.

 

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() }

    var dnaArr = IntArray(4){0}	// 슬라이딩 윈도우할 부분 문자열의 ACGT 갯수
    conditionArr = IntArray(4){0}	// 비밀번호에 충족 ACGT 갯수
    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
    for (i in 0 until  n) {
        tmpDnaArr = removeDna(dna[i], tmpDnaArr)
        tmpDnaArr = addDna(dna[p+i], 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
}