Uknow's Lab.
article thumbnail

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

 

12891번: DNA 비밀번호

평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”

www.acmicpc.net

 

난이도 : 실버 2
태그 : 문자열, 슬라이딩 윈도우 

 

 

설명

슬라이딩 윈도우란 고정 크기의 구간을 이동하며 윈도우 내 데이터를 탐색하는 기법입니다.

투 포인터와 비슷한 원리로 작동합니다.

 

본 문제에서는 항상 고정된 p 사이즈 만큼의 구간만을 탐색하기 때문에,

첫 0 ~ p구간 까지 각각 A, C, G, T의 개수를 카운팅 한 뒤,

구간을 하나씩 이동하며 A, C, G, T의 개수를 증가/감소 시켜주며 풀이할 수 있었습니다.

 

 

소스코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val (s, p) = readLine().split(" ").map { it.toInt() }
    val str = readLine()

    val st = StringTokenizer(readLine())
    val (needA, needC, needG, needT) = Array(4) { st.nextToken().toInt() }
    var (cntA, cntC, cntG, cntT) = arrayOf(0, 0, 0, 0)

    var ptr = p
    var ans = 0

    repeat(p) {
        when (str[it]) {
            'A' -> cntA++
            'C' -> cntC++
            'G' -> cntG++
            'T' -> cntT++
        }
    }

    if (needA <= cntA && needC <= cntC && needG <= cntG && needT <= cntT) ans++

    while (s > ptr) {
        when (str[ptr]) {
            'A' -> cntA++
            'C' -> cntC++
            'G' -> cntG++
            'T' -> cntT++
        }

        when (str[ptr - p]) {
            'A' -> cntA--
            'C' -> cntC--
            'G' -> cntG--
            'T' -> cntT--
        }

        if (needA <= cntA && needC <= cntC && needG <= cntG && needT <= cntT) ans++
        ptr++
    }
    println(ans)
}

 

 

후기

슬라이딩 윈도우 문제는 처음 접해보는데,

투 포인터의 작동 원리와 비슷해 그리 어렵지 않게 풀었던 것 같습니다.

profile

Uknow's Lab.

@유노 Uknow

인생은 Byte와 Double 사이 Char다. 아무말이나 해봤습니다.