[Kotlin] 백준 20437번 - 문자열 게임 2

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

20437번: 문자열 게임 2

유형

Map 자료구조

풀이

구하고자 하는 것

(1) 어떤 문자를 정확히 k개 포함하는 가장 짧은 문자열의 길이,

(2) 어떤 문자를 정확히 k개 포함하면서 그 문자가 앞,끝에 있는 문자열 중 가장 긴 것의 길이

 

(1)의 경우에도 가장 짧으려면 맨 앞, 뒤에 해당 문자가 있어야 한다. 따라서, 앞, 뒤에 어떤 문자가 있으면서 그 문자가 k개 있는 문자열의 가장 긴 것과 가장 짧은 것의 길이를 구해야 한다. 

아이디어

문자열의 앞에서부터 문자를 확인하면서 Map이나 배열에서 그 문자의 원소에 인덱스를 추가한다.

ex) "abca"

count['a'] = {0,3}, count['b'] = {1}, count['c'] = {2}

그러다가 어떤 문자의 인덱스 개수가 k개 이상이 되면, 그 문자를 발견할 때마다 그 인덱스에서 k번째 이전의 인덱스를 빼서 문자열의 길이를 계산한다. 그리고 그것을 가장 긴 문자열과 가장 짧은 문자열의 길이와 비교해서 갱신한다. 

for (i in str.indices) {
    val letter = str[i] - 'a'
    val idxList = idxListOfLetter[letter]
    idxList.add(i)

    // 해당 문자를 k개 이상 발견했을 때
    if (idxList.size >= k) {
        val length = i - idxList[idxList.size - k] + 1=
        shortestLength = length.coerceAtMost(shortestLength)=
        longestLength = length.coerceAtLeast(longestLength)
    }
}

전체 코드

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val t = readLine().toInt()
    val answer = StringBuilder()

    repeat(t) {
        val idxListOfLetter = Array(26) { mutableListOf<Int>() } // 각 문자가 발견된 인덱스를 저장하는 리스트
        val str = readLine()
        val k = readLine().toInt()
        var shortestLength = 10_001 // k개를 포함하는 가장 짧은 문자열 길이(3번)
        var longestLength = k - 1   // k개를 포함하고 앞,끝 문자가 해당 문자인 가장 긴 문자열 길이(4번)

        for (i in str.indices) {
            val letter = str[i] - 'a'
            val idxList = idxListOfLetter[letter]
            idxList.add(i)

            // 해당 문자를 k개 이상 발견했을 때
            if (idxList.size >= k) {
                val length = i - idxList[idxList.size - k] + 1
                // 가장 짧은 길이로 갱신 (3번)
                shortestLength = length.coerceAtMost(shortestLength)
                // 첫번째와 마지막 문자가 같은 문자열 중 가장 긴 걸로 갱신 (4번)
                longestLength = length.coerceAtLeast(longestLength)
            }
        }

        if (shortestLength == 10_001) { // 갱신이 안됐다 -> 어떤 문자가 k개인 문자열이 없다
            answer.append(-1).appendLine()
        } else {
            answer.append(shortestLength).append(' ').append(longestLength).appendLine()
        }
    }

    print(answer)
}