https://www.acmicpc.net/problem/12891
난이도 : 실버 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)
}
후기
슬라이딩 윈도우 문제는 처음 접해보는데,
투 포인터의 작동 원리와 비슷해 그리 어렵지 않게 풀었던 것 같습니다.
'코딩테스트 > Kotlin' 카테고리의 다른 글
[백준 2902번] [Kotlin] KMP는 왜 KMP일까? (0) | 2023.03.28 |
---|---|
[백준 9379번] [Kotlin] 미확인 도착지 (0) | 2023.03.28 |
[백준 26517번] [Kotlin] 연속인가?? (0) | 2023.03.26 |
[백준 1010번] [Kotlin] 다리 놓기 (0) | 2023.03.26 |
[백준 13305번] [Kotlin] 주유소 (0) | 2023.03.26 |