[문자열 / Kotlin] 2020 KAKAO BLIND RECRUITMENT - 문자열 압축

풀이 언어

Kotlin

코드

fun solution(s: String): Int {
    var minLength = s.length

    for (i in 0 until s.length / 2) {
        var subString = s.slice(0..i)
        var answer = ""
        var cnt = 1
        var last = 0

        for (j in i + 1 until s.length - i step i + 1) {
            // 마지막 Index 를 저장한다.
            last = j + i + 1
            // 같은 SubString 인 경우 이를 카운트한다.
            if (subString == s.slice(j..j + i)) cnt += 1
            // 다른 SubString 인 경우
            else {
                if (cnt > 1) {
                    // 숫자 + SubString 으로 변환한다.
                    answer += cnt.toString() + subString
                } else {
                    answer += subString
                }
                // SubString 을 새롭게 설정한다.
                subString = s.slice(j..j + i)
                cnt = 1
            }
        }

        // 한 번 더 진행한다.
        if (cnt > 1) {
            answer += cnt.toString() + subString
        } else {
            answer += subString
        }

        // 남아 있는 문자열을 추가한다.
        answer += s.slice(last until s.length)

        // 문자열의 크기를 비교한다.
        if (minLength > answer.length) minLength = answer.length
    }
    return minLength
}

풀이 방법

이 문제에서 가장 중요한 것은 문자열을 Slice 할 때 모두 같은 크기만큼 나누어야한다는 것이다. 마지막 테스트 케이스를 보면 xababcdcdababcdcd (17자) 로 되어있는데 x / ababcdcd/ ababcdcd 이런 식으로 끊으면 x2ababcdcd 로 압축될 것처럼 보인다. 하지만 모두 같은 크기만큼 나누어야한다는 규칙이 있으므로 이런 식으로 나누는 것은 불가능하다. 이를 염두하고 문제를 해결해보자. 로직은 단순하다. 문자열을 특정한 크기에 따라 Slice 를 진행하면 된다.

 

1. 이 때, 문자열을 나누는 SubString의 크기는 1 ~ 문자열의 크기/2 가 될 수 있다.

2. 각 크기에 따라 완전 탐색을 진행한다.

3. 위에서 설정한 SubString과 같은 SubString 이 발견되면 이를 카운트한다.

4. 다른 SubString 이 나온 경우 위에서 카운트한 SubString을 숫자 + SubString으로 치환한다.

5. 다른 SubString 을 새로운 SubString 으로 설정하고 잡고 탐색을 계속한다.

 

탐색 완료 이후에 남은 문자열이 있을 수 있다. 이를 위해 마지막 Index 를 저장하고 이를 활용해서 남은 문자열을 더 해주는 조건을 추가했다.

결과