[LeetCode] Reverse String

https://leetcode.com/problems/reverse-string

문제

Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:
Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:
Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Constraints:
- 1 <= s.length <= 10⁵
- s[i] is a printable ascii character.

고민

해당 문제는 주어진 문자 배열을 거꾸로 배치하여 반환하는 것이다.
하지만 조건이 있다. `in-place` 즉, 새로운 배열이 아닌 주어진 배열에서 처리하여 진행해야하는 것이다.

단순하게 생각했을 때에는 그냥 reversed 처리하면 되지 않을까? 라는 생각을 하였다.
하지만, reversed 메소드를 보면,

/**
 * Returns a list with elements in reversed order.
 */
public fun <T> Iterable<T>.reversed(): List<T> {
    if (this is Collection && size <= 1) return toList()
    val list = toMutableList()
    list.reverse()
    return list
}

또 다른 List 객체를 하나 만들게 되고, 실제 reverse 하는 함수를 또 다시 찾아 보면

/**
 * Reverses elements in the list in-place.
 */
public actual fun <T> MutableList<T>.reverse(): Unit {
    java.util.Collections.reverse(this)
}

/**
 * Reverses the order of the elements in the specified list.<p>
 *
 * This method runs in linear time.
 *
 * @apiNote
 * This method mutates the specified list in-place. To obtain a
 * reverse-ordered view of a list without mutating it, use the
 * {@link List#reversed List.reversed} method.
 *
 * @param  list the list whose elements are to be reversed.
 * @throws UnsupportedOperationException if the specified list or
 *         its list-iterator does not support the {@code set} operation.
 * @see    List#reversed List.reversed
 */
@SuppressWarnings({"rawtypes", "unchecked"})
public static void reverse(List<?> list) {
    int size = list.size();
    if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
            swap(list, i, j);
    } else {
        // instead of using a raw type here, it's possible to capture
        // the wildcard but it will require a call to a supplementary
        // private method
        ListIterator fwd = list.listIterator();
        ListIterator rev = list.listIterator(size);
        for (int i=0, mid=list.size()>>1; i<mid; i++) {
            Object tmp = fwd.next();
            fwd.set(rev.previous());
            rev.set(tmp);
        }
    }
}

모든 요소를 하나씩 확인하여 처리함으로 시간 복잡도에서 O(N)로 처리하게 된다.

이미 새로운 List 객체를 만드는 것에서 조건에 부합하지 않는다.

해결

class Solution {
    fun reverseString(s: CharArray): Unit {
        var start = 0
        var end = s.size - 1
        while (start <= end) {
            val temp = s[start]
            s[start] = s[end]
            s[end] = temp
            start++
            end--
        }
    }
}

새로운 객체 또는 새로운 공간을 사용하지 않아야 하기 때문에 덮어쓰는 방식으로 해결했다.

얼핏 보면 이진탐색처럼 보이지만, 이진 탐색을 활용하여 처리하였다.
모든 요소를 거꾸로 넣어야하기때문에 첫번째 요소 자리에 제일 끝 요소를 넣고, 두번째 요소 자리에 끝에서 두번째 요소를 넣는 식으로 활용한 것이다.

결과

후기

사실은 원래 reversed를 사용했었다.
오래걸리더라도 solved 가 되면 개선을 해야겠다라는 마음으로 reversed를 활용하여 solved 를 했다.

하지만 결과가 너무 처참하기에 Collections 파일에 들어가서 코드를 확인해봐야만 했었다... 

코드를 확인해보고 띠용-! 되어서 다른 방식으로 접근한 것이다.
무언가 찾을 때 순차적으로 찾아야 된다라는 고정 관념을 벗어버려야겠다.