[Kotlin, S1] 백준 5525번 IOIOI

출처: unsplash.com

 

IOIOI(5525번)

Silver 1

#문자열

 

문제 내용

 

 

문제 접근

첫 줄의 입력으로 O가 몇 개 들어 있는지 확인한다.

예를 들어 O = 1이면 IOI, O = 3이면 IOIOIOI이 된다. 다음과 같은 문자열을 IOI 문자열이라고 부르겠다.

IOI 문자열이 3번째 줄에 입력되어 있는 문자열에 몇 개가 포함되어 있는지 구해야 한다.

IOI 문자열이 IOIOI이고, 문자열이 IIOIOIOIIOO일 때는,

1. IIOIOIOIIOO

2. IIOIOIOIIOO

로 총 2가지의 경우를 구할 수 있다. 겹치는 경우까지 생각해야 한다.

 

IOI문자열은 처음에 I로 시작하고 쭉 계속 OI가 반복된다는 규칙이 있다.

O = 1일 때 IOI,

O = 3일 때 IOIOIOI 인 것처럼.

이를 이용해 처음에 시작 문자가 I로 시작하고, 그다음에 OI가 연속되는지 체크하면 된다.

 

예제 입력 1의 3번째 줄의 문자열을 예로 들어 보겠다.

OOIOIOIOIIOII

다음과 같은 문자열에서 위에서 언급한 방식을 적용해 보자.

사진 1-1

s는 입력 문자열을 하나씩 확인하는 것이다.

check는 현재 문자열이 OI가 반복되는지 확인하는 것이다. 처음에 I가 시작되면 현재 문자열을 체크하기 시작한다.

ioCnt는 최종 연속된 OI의 개수를 나타낼 것이다. 연속 OI가 끊기면 새로운 필드를 생성해 그 필드에 새로 기록한다.

 

위의 예제의 결과를 표로 나타내 봤다. ioCnt를 보고 현재 IOI 문자열과 비교를 해서 값을 구해줄 수 있다.

위 표의 ioCnt는 3, 1, 0이다. 0인 경우를 빼면 3, 1만 남는다.

여기서 O = 1인 경우에는 공간을 1씩 차지하기 때문에 포함된 개수는 4개가 된다.

O = 2인 경우는 경우가 약간 다르다.

3에서 공간을 2씩 차지하기 때문에 경우의 수가 2가지가 된다. [1, 2]와 [2, 3]이다. 문자가 연속되어 있어야 하기 때문에 [3, 1]은 안된다.

다음의 1은 공간 2보다 부족하기 때문에 넘기면 최종적인 포함 개수는 2개가 된다.

 

이제 check와 ioCnt가 변경되기 위해 어떤 조건이 필요한지 코드를 이용해서 확인해 보자.

 

<조건 1>

check는 처음에 첫 I가 들어오기 전까지는 빈 문자열로 존재한다.

첫 I가 들어왔음을 나타낼 변수를 firstI로 지정해 주겠다.

firstI가 true여야 하고, 첫 문자는 O여야 한다. OI순서대로 연속돼야 하기 때문이다. 또한 check도 비어 있는 상태여야 한다.

이를 코드로 나타내면 다음과 같다.

if (firstI && string[i] == 'O' && check.isEmpty())

 

<조건 2>

이제 조건 1을 만족했으면 check에 O가 들어온 상태일 것이다.

조건 1과 마찬가지고 firstI가 true여야 하는 건 같고, 다음 문자로는 I가 와야 한다. 또한 check의 현재 마지막 문자가 O여야 한다.

혹시 모를 보험으로 check가 비어있지 않아야 하는 조건도 같이 추가하자.

이를 코드로 나타내 볼까?

else if (check.isNotEmpty() && firstI && string[i] == 'I' && check.last() == 'O')

 

<조건 3>

조건 1, 2를 만족하지 못하면 이제 조건 3으로 넘어와야 한다.

조건 3에는 사진 1-1에 I가 연속해서 나타났을 때처럼 check를 clear 시켜 줘야 한다.

또한 I가 연속해서 나타나는 경우도 있고, O가 연속해서 나타날 수도 있을 것이다.

만약 I가 연속해서 나타난다면 firstI를 true로 계속 살려놔도 상관없지만, 만약 O가 연속해서 나타난다면 firstI를 false로 변경해야 한다.

또한 이미 연속된 값이 들어가 ioCntList에 값이 들어간 경우에는 다음 index에 값이 들어갈 수 있도록 처리해주어야 한다.

else {
    check.clear()
    if (string[i] != 'I') firstI = false
    if (ioCntList[ioCntIndex] != 0) ioCntList++
}

 

 

<조건 4>

조건 4는 상시로 확인해야 하는 조건이다.

check가 OI인지 확인해 줘야 한다. 만약 조건을 만족하면 check를 clear 시켜주고, 현재 연속된 OI의 개수를 저장하는 ioCntList를 늘려 준다.

if (check.toString() == "OI") {
    check.clear()
    ioCntList[ioCntIndex]++
}

위 조건 4개를 이용해 코드로 구현해 보자.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val oCnt = readLine().toInt()
    val stringLength = readLine().toInt()
    val string = readLine()

    val checkString = StringBuilder()
    for (i in 1 .. oCnt * 2 + 1) {
        checkString.append(
            if (i % 2 == 0) "O"
            else "I"
        )
    }


    val check = StringBuilder()     // 현재 문자열을 직접 받으면서 체크함.
    val ioCntList = MutableList(stringLength) { 0 }     // OI가 얼마나 연속되어서 나타나는지 확인.
    var ioCntIndex = 0  // ioCntList에 값이 추가될 index
    var firstI = false  // OI를 체크하기 전에 첫 번째에 I가 있는지 확인.
    for (i in 0 until stringLength) {
        if (!firstI && string[i] == 'I') firstI = true

        if (firstI && string[i] == 'O' && check.isEmpty()) check.append("O")
        else if (check.isNotEmpty() && firstI && string[i] == 'I' && check.last() == 'O') check.append("I")
        else {
            check.clear()
            if (string[i] != 'I') firstI = false
            if (ioCntList[ioCntIndex] != 0) ioCntIndex++
        }

        if (check.toString() == "OI") {
            check.clear()
            ioCntList[ioCntIndex]++
        }
    }

    var res = 0
    for (i in 0 until ioCntList.size) {
        if (ioCntList[i] == 0) break

        if (ioCntList[i] >= oCnt)
            res += ioCntList[i] - (oCnt - 1)
    }

    println(res)
}

 

문제 풀이

처음에 입력된 O의 개수(oCnt)에 맞게 IOI 문자열을 생성한다.

그다음 입력받은 문자열을 돌면서 OI가 연속되는지 확인한다.

조건을 확인하기 전에 먼저 firstI를 변경해줘야 한다. I로 시작하는 순간 firstI를 true로 바꿔준다.

 

조건 1을 통해 check에 O를 넣어 주고, 조건 2를 통해 I를 넣어 준다.

조건 3에서는 연속된 OI가 끊겼을 때 로직을 처리한다.

조건 4는 상시로 확인하며, chek가 OI라면 check를 clear 시키고 ioCntList를 늘려 준다.

 

 

문제 해결 과정

처음에는 반복에 subString을 이용해 풀었지만 시간 초과로 100점을 맞지 못했다.

그래서 다른 사람의 문제 접근법을 간략하게 찾아봐서 OI가 반복된다는 것을 알게 되고 그에 맞게 반복된 OI의 개수를 구해 문제를 해결할 수 있었다.