<백준> 문자열 게임 2

[백준]

20437번: 문자열 게임 2

[깃허브]

ForCodeKata/baekjoon 문제집/문자열 게임 2 at main · heesoo-park/ForCodeKata

제출결과

---

 

시간복잡도를 계산했을 때 구상한 방법이 안 된다는 걸 알지만 그것말고는 방법이 떠오르지 않아서 일단 구현한 문제였다.

처음에는 2중 for문을 이용해서 모~~든 케이스(부분문자열)를 가지치기 없어 다 도는 로직이 나왔다.

당연히 최대 숫자 제한이 10000이었기 때문에 O(N^2)의 시간복잡도와 만나 시간초과가 떴다.

 

이렇게 시간초과를 맞고 어떻게 접근해야할까 하는데 슬라이딩 윈도우라는 단어가 보였고 이를 어떻게 접목시켜야하나 고민을 시작했다.

또한 가지치기가 필수라고 생각이 들어서 이 부분도 고민했다.

※ 슬라이딩 윈도우 알고리즘
고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘

 

슬라이딩 윈도우는 보통 고정된 크기로 움직이며 원하는 값을 구하는데 이 문제에서는 조금 느낌이 다르게 사용해야해서 잘 떠오르지 않더라

가지치기는 사실 K개보다 적은 알파벳을 빼는 방식만 취하면 될 거였다.

 

그렇게 나온 방식은 부분문자열을 구하는 방식이 아니라 특정 위치에서 시작하여 한칸씩 옆의 값을 보면서 범위 내에 특정 위치의 알파벳의 개수가 K개가 됐을 때 구해야하는 조건 값과 비교하여 값을 업데이트하는 방식이었다.

값은 범위(오른쪽 - 왼쪽 + 1)로 업데이트한다.

 

입력받은 문자열에서 문자의 개수를 가지고 필터링(가지치기)하기 위해 groupingBy와 eachCount, filter를 사용했다.

val counting = str.groupingBy { it }.eachCount().filter { it.value >= k }.keys

이렇게 하면 개수가 k개 이상인 알파벳들의 집합이 반환된다.

 

값 비교하는 건 coerceAtMost와 coerceAtLeast를 사용했다.

for (j in i + 1 until str.length) {
    if (str[i] == str[j]) cnt++

    if (cnt == k) {
        shortest = shortest.coerceAtMost(j - i + 1)
        longest = longest.coerceAtLeast(j - i + 1)
        break
    }
}

처음에는 Math.max와 Math.min을 사용했는데 IDE 자체에서 Kotlin 기반 함수를 추천하더라

이거 말고도 minOf, maxOf, minBy, maxBy 등 더 있다.

 

값의 범위를 강제하는 함수라고 한다.

※ coerceAtLeast
호출된 객체가 특정 객체보다 큰 지 아닌지를 확인
호출된 객체가 더 크면 객체를 반환, 아니면 최소 객체를 반환

※ coerceAtMost
호출된 객체가 특정 객체보다 작은 지 아닌지를 확인
호출된 객체가 더 작으면 객체를 반환, 아니면 최대 객체를 반환

 

해당 방법으로 작성한 코드는 다음과 같다.

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

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

    repeat(t) {
        val str = readln()
        val k = readln().toInt()
        var shortest = Int.MAX_VALUE
        var longest = Int.MIN_VALUE

        if (k == 1) {
            bw.write("1 1\n")
        } else {
            val counting = str.groupingBy { it }.eachCount().filter { it.value >= k }.keys
            if (counting.isNotEmpty()) {
                for (i in str.indices) {
                    if (str[i] !in counting) continue

                    var cnt = 1
                    for (j in i + 1 until str.length) {
                        if (str[i] == str[j]) cnt++

                        if (cnt == k) {
                            shortest = shortest.coerceAtMost(j - i + 1)
                            longest = longest.coerceAtLeast(j - i + 1)
                            break
                        }
                    }
                }

                bw.write("$shortest $longest \n")
            } else {
                bw.write("-1\n")
            }
        }
    }

    bw.flush()
    bw.close()
}

 

참고)

https://moonsbeen.tistory.com/351