[알고리즘 스터디] Reverse String

LeetCode - 344. Reverse String

[LeetCode - 344. Reverse String]

입력된 Char Array의 순서를 거꾸로 뒤집으면 되는 문제이다.

return값이 없이 직접 배열을 바꾸면 된다.

class Solution {
    fun reverseString(s: CharArray): Unit {
        var f = 0
        var e = s.size - 1

        while(f < e) {
            val temp = s[f]

            s[f] = s[e]
            s[e] = temp

            f++
            e--
        }
    }
}

입력된 값을 뒤집기만 하며 되기 때문에 reverse() 함수를 사용해 변경하면 간단한 문제지만, 해당 방식으로 풀었을 경우 Runtime이 아무리 빨라도 250ms이하로 내려가긴 힘들다.

실제로 reverse()함수가 어떻게 구성되었는지 확인해보면 위의 방식과 별로 다르지 않지만, 함수가 한 번 더 호출되는 과정에서 약간의 오버헤드가 발생하게 된다.

// 실제 reverse 함수의 내부
public fun CharArray.reverse(): Unit {
    val midPoint = (size / 2) - 1
    if (midPoint < 0) return
    var reverseIndex = lastIndex
    for (index in 0..midPoint) {
        val tmp = this[index]
        this[index] = this[reverseIndex]
        this[reverseIndex] = tmp
        reverseIndex--
    }
}

문제를 푸는 이유도 reverse()함수를 사용하는것보다 직접 구현하는걸 목적으로 하는 것 같아서 직접 코드를 작성했다.

추가적인 함수 호출이 없을 경우 확실히 Runtime이 줄어드는것이 보였다.

마지막 Index구하기

이 과정에서 배열의 마지막 Index값을 구하기 위해 lastIndex속성을 사용했는데, 이 과정에서 위와 같은 오버헤드가 발생한다는것을 알게되었다.

lastIndex는 내부적으로 array.size - 1을 반환하는데, 이 과정에서 약간의 오버헤드가 발생하게 되고, 실제로 size - 1로 사용했을 때 정말 극도로 미세하지만 차이가 있다는것을 확인할 수 있었다.

나노초 단위로 들어가게 될 경우 실제로 lastIndex를 사용해 위의 코드를 실행해본 결과 100,000번의 연산시간 평균이 280ns, size - 1로 실행한 경우 37ns로 나노단위의 차이가 존재하긴 했다.