Two Pointers, O(n) 의 복잡도로 문자열 뒤집는 방법 (reverse string)

reverse string

배열 참조를 받아서 해당 배열을 reverse 된 배열로 변환하기

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function (s) {
  let l = 0;
  let r = s.length - 1;

  while (l < r) {
    const tmp = s[l];
    s[l] = s[r];
    s[r] = tmp;

    l += 1;
    r -= 1;
  }
};

순서를 뒤바꾸는 규칙 생각해보기

• 맨 첫번째 문자를 맨 마지막으로 옮긴다.
• 두번째 문자는 맨 마지막에서 두번째로 옮긴다.
• 세번째 문자는 맨 마지막에서 세번째로 옮긴다.
• n 번째 문자는 맨 마지막에서 n 번째로 옮긴다.

즉, 자신이 지금 첫번째 글자에서 n 번째 위치라면 마지막에서 n 번째 위치인 글자와 바꾸면 된다.

맨 마지막 글자와 맨 끝 글자의 포인터에서 시작하여 중간까지 오면 완성된다.