5525번: IOIOI

문제 출처 : https://www.acmicpc.net/problem/5525

5525번: IOIOI

언어 : Kotlin

 

문제 설명 :

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.

• P1 IOI
• P2 IOIOI
• P3 IOIOIOI
• PN IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

• 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.
• S에 PN이 몇 군데 포함되어 있는지 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 256MB

 

• 1 ≤ N ≤ 1,000,000
• 2N+1 ≤ M ≤ 1,000,000
• S는 I와 O로만 이루어져 있다.

 

서브태스크 :

번호	배점	제한
1	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

 

입출력 예 :

입력	출력
2 1 5 10 100 100 11	10
3 2 1 65 5 23 2 99 10 2	164

 

풀이 : 

첫 풀이 50점 짜리.

for문 2개, regionMatches 함수로 인한 속도 문제인가 싶었다.

import java.io.BufferedWriter
import java.io.OutputStreamWriter

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val n = readLine().toInt()
    val m = readLine().toInt()
    val s = readLine()
    var answer = 0

    var pattern = "I"
    repeat(n) {
        pattern += "OI"
    }

    for (i in s.indices) {
        if (s.regionMatches(i, pattern, 0, pattern.length)) answer++
    }

    bw.write("$answer")
    bw.flush()
    bw.close()
}

 

100점 짜리

import java.io.BufferedWriter
import java.io.OutputStreamWriter

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val n = readLine().toInt()
    val m = readLine().toInt()
    val s = readLine()
    var answer = 0
    var cnt = 0

    for (i in 0 .. m - 3) {
        if (s[i] == 'I') {
            if (s[i + 1] == 'O' && s[i + 2] == 'I') {
                cnt++
                if (n <= cnt) answer++
            } else {
                cnt = 0
            }
        }
    }

    bw.write("$answer")
    bw.flush()
    bw.close()
}