[LeetCode] Reverse String(문자열 뒤집기) 개인 풀이

문제

문자열을 뒤집는 메서드를 작성하세요. 주어진 입력은 char 배열입니다.

단, 별도의 array를 생성하면 안되며 입력받은 메모리만을 이용하여 문제를 해결하여야합니다.

또한 char 배열의 내부에는 ascii characters로 표현가능한 문자열들만 있다고 가정합니다.

예제 1

입력 : ["h","e","l","l","o"]
출력 : ["o","l","l","e","h"]

예제 2

입력 : ["H","a","n","n","a","h"]
출력 : ["h","a","n","n","a","H"]

원본 문제 : https://leetcode.com/problems/reverse-string/

개인 풀이

가장 간단하게 떠오르는 풀이방법은 해당 배열의 크기만큼 배열을 하나 더 생성 한 후 하나씩 거꾸로 매핑해주는 방법입니다. 이렇게 풀어내는 방법도 정답입니다. 이렇게 풀어내었을 때는 시간복잡도는 1번씩 돌기 때문에 O(N)이 소모될 것이며 추가적으로 메모리 공간이 O(N)만큼, 즉 입력받을 배열 크기 만큼 한벌 더 필요합니다.

하지만 문제를 보시면 입력받은 메모리만을 이용하여 문제를 해결하라고 되어있습니다. 즉, 위 방법으로 풀면 안된다는 말입니다. 다른 방법을 생각해 봅시다.

또다른 방법으로는 1번째와 마지막을 교환하고 2번째와 마지막 - 1 번째를 교환하고 중간까지 교환하는 방식이 있습니다. 이 방식을 사용하면 시간복잡도는 O(N)이지만 실질적으로는 N/2 만큼 연산이 이루어집니다. 또한 해당 배열에서만 Swap이 이루어지면 되므로 추가적인 메모리도 사용되지 않습니다. 이미지로 나타내면 아래와 같습니다.

해당 문제를 코드로 풀어보겠습니다.

코드

class Solution {

  public void reverseString(char[] s) {
    for (int i = 0; i < s.length / 2; i++) {
      char temp = s[i];
      s[i] = s[s.length - i - 1];
      s[s.length - i - 1] = temp;
    }
  }
}

마무리

오늘은 이렇게 간단한 문자열 뒤집기(Reserve String)에 대해서 알아보는 시간을 가져보았습니다.

감사합니다. :)