[Kotlin] String 압축하기 : 반복되는 문자 압축하기

문제

반복되는 문자를 합쳐서 [문자][반복된 숫자]로 표현하라. 만약 압축된 문자가 원래 문자보다 길다면 원래 문자를 반환하라

 

예1) aaabbccc -> a3b2c3

예2) abbc -> abbc : a1b2c1 보다 원래 문자가 더 짧으므로

 

문제 풀기 전 확인 사항

- String에 스페이스가 있는가?

- 같은 길이면 어떻게 하는가?

 

문제 풀이

- string의 첫 Char로 초기화 하고 포인터를 1씩 증가시키면서 같은 Char이 나오는지 확인해야 한다.

- 같은 Char이 나오면 counter을 1씩 증가시킨다.

- 다른 Char이 나오면 StringBuilder에 추가한다. 

class Solution() {
    fun compress(string: String) : String {
        var pointer = 0
        var currentChar : Char = '\u0000'
        var counter = 0
        val stringBuilder = StringBuilder("")

        for (char in string) {
            if (pointer == 0) {
                currentChar = char
                counter = 1
                pointer += 1
                continue
            }

            if (currentChar == char) {
                counter += 1
            } else {
                stringBuilder.append(currentChar)
                stringBuilder.append(counter)

                currentChar = char
                counter = 1
            }

            pointer += 1
        }

        stringBuilder.append(currentChar)
        stringBuilder.append(counter)

        val compressedString = stringBuilder.toString()

        return if (compressedString.length >= string.length) {
            string
        } else {
            compressedString
        }
    }
}

 

복잡도

string길이를 N이라고 하면

시간 복잡도 : O(N) - string의 Char 을 한 번만 순환하므로. 

공간 복잡도 : O(N) - pointer, counter, currentChar은 상수지만, stringBuilder에 최대 N개의 문자가 추가될 수 있으므로. 여기서 주의할 것은 StringBulider을 사용해 문자 공간 차지가 중복해서 일어나지 않도록 한다. StringBuilder 대신 String을 사용하면 문자가 계속 복사되어 O(N^2)이 되어버린다.

 

 

테스트 케이스

엣지 케이스 테스트를 위해 다음의 테스트 케이스를 만든다.

- 압축된 문자열이 더 짧을 경우

- 압축된 문자열과 원래 문자열이 같은 경우 : aab 

- 압축된 문자열이 더 길 경우 : a

- 빈 문자열

fun main() {
    val solution = Solution()
    println(solution.compress("aaabbcc")) // a3b2c2
    println(solution.compress("aabb")) // aabb
    println(solution.compress("a")) // a
    println(solution.compress("")) // 
}