[Kotlin] 공백을 "%20"으로 대체해 Url로 만들기

문제

문자열에 들어았는 모든 공백을 %20으로 바꾸기. %20으로 바꾸었을 때만큼의 크기를 가진 문자열(String 혹은 CharArray)과, 실제 문자열의 크기(size)가 주어진다.

문제 풀기 전 확인 사항

1. input은 String인가 아니면 CharArray인가?

문제 풀이1

input이 String이라고 가정하면, 아래와 같이 풀 수 있다.  Kotlin의 String은 Immutable 하기 때문에, String에서 CharArray를 가져오려면 새로운 CharArray를 할당해야 하므로 아래와 같이 새로운 공간을 할당해야 한다.

class Solution() {
    fun urlify(input: String, size: Int): String {
        var charArrayIndex = 0
        val charArray = CharArray(input.length)
        var index = 0

        for (char in input) {
            if (index == size) break
            if (char == ' ') {
                charArray[charArrayIndex] = '%'
                charArray[charArrayIndex + 1] = '2'
                charArray[charArrayIndex + 2] = '0'
                charArrayIndex += 3
            } else {
                charArray[charArrayIndex] = char
                charArrayIndex += 1
            }
            index += 1
        }
        return String(charArray)
    }
}

복잡도

size가 N이라 했을 때 

시간 복잡도: O(N) - 한 번만 for문을 돌면 되므로

공간 복잡도: O(N) - 최대 3N만큼의 공간이 생성되므로 

문제 풀이2

input이 CharArray라고 한다면, 아래와 같이 풀 수 있다. 실제 문자 크기인 size를 사용해 CharArray에서 마지막 문자열부터 하나씩 처리해서 채워나가는 방식으로 처리한다.

class Solution2() {
    fun urlify(input: CharArray, size: Int): CharArray {
        var currentIdx = input.size - 1

        for (index in size - 1 downTo 0) {
            val value = input[index]
            if (value == ' ') {
                input[currentIdx] = '0'
                input[currentIdx - 1] = '2'
                input[currentIdx - 2] = '%'
                currentIdx -= 3
            } else {
                input[currentIdx] = value
                currentIdx -= 1
            }
        }

        return input
    }
}

복잡도

size가 N이라 했을 때 

시간 복잡도: O(N) - 한 번만 for문을 돌면 되므로

공간 복잡도: O(1) - 추가 공간을 사용하지 않았으므로

테스트 케이스

• 양쪽에 문자가 있는 케이스
• 모두 공백인 케이스
• 한쪽만 공백인 케이스

fun main() {
    val solution = Solution2()
    println(solution.urlify("Mr Dev Cho    ".toCharArray(), 10))
    println(solution.urlify("         ".toCharArray(), 3))
    println(solution.urlify("A   ".toCharArray(), 2))
}