백준 20437 문자열 게임 2 Kotlin (슬라이딩 윈도우)

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

20437번: 문자열 게임 2

문제

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
2. 양의 정수 K가 주어진다.
3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위와 같은 방식으로 게임을 T회 진행한다.

입력

문자열 게임의 수 T가 주어진다. (1 ≤ T ≤ 100)

다음 줄부터 2개의 줄 동안 문자열 W와 정수 K가 주어진다. (1 ≤ K ≤ |W| ≤ 10,000) 

출력

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.

만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

알고리즘 분류

• 문자열
• 슬라이딩 윈도우

풀이

문자열, 슬라이딩 윈도우 문제이다.

3번 조건에 해당하는 문자열이 없다면 4번 문자열도 당연히 없기 때문에 그냥 K개 이상인 문자가 없다면 -1을 출력하면 된다.

풀이는 다음과 같다.

주어진 문자열에서 a~z까지 문자 별로 해당 문자의 인덱스들을 ArrayList에 각각 저장한다.

만약 abbababaa라는 문자열이 있다면

charPositionArr[0] 배열은 다음과 같다.

0	1	2	3	4
0	3	4	7	8

위 배열의 의미는 a라는 문자에 대해 앞에서부터 순서대로 문자열에서의 position을 의미한다.

즉 charPositionArr[0][2] - charPositionArr[0][0]는 a를 3개 포함하는 길이를 의미한다.

따라서 모든 문자 a~z에 대해 포지션들을 저장해 놓고 슬라이딩 윈도우의 사이즈를 k만큼 잡아서 maxLen(4번 조건) minLen(3번 조건)을 구하여 출력한다.

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

fun getMinAndMax(list: ArrayList<Int>, len: Int): Pair<Int, Int> {
    var min = Int.MAX_VALUE
    var max = -1
    if (list.size >= len) {
        for (i in 0..list.size - len) {
            min = min.coerceAtMost(Math.abs(list[i] - list[i + len - 1]) + 1)
            max = max.coerceAtLeast(Math.abs(list[i] - list[i + len - 1]) + 1)
        }
    }
    return Pair(min, max)
}

fun main() = with(System.out.bufferedWriter()) {

    val t = getInt()
    repeat(t) {
        //input
        val str = br.readLine()
        val k = getInt()
        val charPositionArr = Array(26) { ArrayList<Int>() }

        var minLen = Int.MAX_VALUE
        var maxLen = -1
        //문자별 position 저장
        for (i in str.indices) {
            val ch = str[i]
            charPositionArr[ch - 'a'].add(i)
        }
        for (i in 0 until 26) {
            val (min, max) = getMinAndMax(charPositionArr[i], k)
            minLen = minLen.coerceAtMost(min)
            maxLen = maxLen.coerceAtLeast(max)
        }
        if (minLen == Int.MAX_VALUE) write("-1\n")
        else write("$minLen $maxLen\n")
    }
    close()
}