자바 문자열 역순 뒤집기 4가지 방법

문자열을 뒤집는 4가지 방법에 대해 소개한다. 결과적으로StringBuilder를 사용해 문자열을 조작하는 일이 대부분이겠지만 그래도 밑단의 알고리즘이 돌아가는 원리를 이해해보는 취지에서 여러 가지 방법을 생각해보았다. 

 

 

 

1. 단순 반복문 이용 

 

단순 반복문을 이용하여 뒤에서부터 탐색하고 하나씩 새로운 String으로 만든다. 

 

다음 메서드는 하나의 매개변수 word를 받으며, 이를 뒤집어 리턴한다.

public static String reverse(String word) {
   StringBuilder stringBuilder = new StringBuilder();
   for (int i = word.length() - 1; i >= 0; i--) {
      stringBuilder.append(word.charAt(i));
   }

   return stringBuilder.toString();
}

 

동작 원리 

메서드 내부에서는 StringBuilder 객체인 stringBuilder를 생성합니다. String의 Immutable 속성 때문에 새로운 문자열을 "+" 방식으로 반복문 내부에서 생성한다면 문자열이 커짐에 따라 효율이 상당히 떨어진다. StringBuilder는 스트링 객체를 계속해서 생성하는 방식으로 문자열을 만들지 않기 때문에 보다 효율적으로 새로운 문자열을 만들 수 있다.

 

StringBuilder와 String 클래스의 문자열 만드는 효율 차이 

 

그 다음, for 반복문을 사용하여 word 문자열을 뒤에서부터 앞으로 순회한다. i 변수는 word.length() - 1부터 시작하여 0까지 감소하면서 반복된다. 즉, 문자열의 마지막 문자부터 첫 번째 문자까지 순회한다.

반복문의 각 단계에서, stringBuilder.append(word.charAt(i))에서 word 문자열에서 i번째 위치에 있는 문자를 stringBuilder에 추가한다. 이를 통해 word 문자열을 거꾸로 된 순서로 stringBuilder에 추가하게 된다.

반복문이 모두 완료되면, stringBuilder.toString()을 호출하여 stringBuilder에 있는 문자열을 문자열 형태로 변환하고 이를 반환한다.

결과적으로 reverse("Hello")는 "olleH"를 반환한다.

 

시간복잡도 

주어진 문자열의 길이를 N이라고 할 때, for 루프를 통해 문자열을 역순으로 생성하는 과정이 수행되므로 시간 복잡도는 O(N)이다.

 

장점

익숙함 

 

단점 

StringBuilder를 사용하여 문자열을 구축한다. 이때 추가적인 메모리 사용이 필요하다.

 

 

 

2. 배열과 스왑을 이용한 방법

 

다음 방법은 문자열을 문자 배열로 변환한 후, 배열의 앞과 뒤의 문자를 스왑하여 뒤집는 방법이다.

 

public static String reverse2(String word) {
   char[] characters = word.toCharArray();
   int start = 0;
   int end = word.length() - 1;

   while (start < end) {
      swap(characters, start, end);
      start++;
      end--;
   }

   return new String(characters);
}

private static void swap(char[] characters, int start, int end) {
   char temp = characters[start];
   characters[start] = characters[end];
   characters[end] = temp;
}

동작 원리 

위의 코드는 입력된 문자열을 문자 배열(char[])로 변환한 후, 배열의 시작 인덱스(start)와 끝 인덱스(end)를 사용하여 배열의 앞과 뒤의 문자를 스왑하는 과정을 반복한다. 

 

반복문은 start가 end보다 작은 동안 계속 실행된다. 반복할 때마다 start는 증가하고 end는 감소한다. swap 메서드는 배열의 start 인덱스와 end 인덱스에 있는 문자를 서로 스왑한다.

 

예를 들어, 입력된 문자열이 "Hello"인 경우, 문자 배열은 ['H', 'e', 'l', 'l', 'o']가 된다. 초기에 start는 0을, end는 문자열의 길이에서 1을 뺀 값인 4를 가리킨다. 반복문이 실행되면서 start와 end의 위치가 이동하면서 문자 배열의 요소들이 스왑된다. 반복문이 종료되면 문자 배열은 ['o', 'l', 'l', 'e', 'H']가 되고, 이를 다시 문자열로 변환하여 반환한다.

 

 

시간복잡도 

 

입력된 문자열을 문자 배열로 변환하는 과정이 필요하며, 이후 반복문을 통해 문자 배열을 뒤집는다. 문자열의 길이를 N이라고 할 때, 문자열을 문자 배열로 변환하는 시간 복잡도는 O(N)이다.

 

반복문을 통해 문자 배열을 뒤집는 과정은 배열의 절반 길이만큼 반복되므로 O(N/2)이므로 최종 시간 복잡도는 O(N)이다.

 

장점

문자열을 직접 뒤집는 것이 아니라 문자 배열을 수정하므로 StringBuilder를 사용하는 것보다 메모리 효율이 높다.

 

단점 

문자열의 길이가 긴 경우 문자 배열로 변환하는 과정에서 메모리 사용량이 늘어날 수 있다.

 

 

 

3. StringBuilder의 reverse 메서드를 이용한 방법

 

StringBuilder 클래스는 reverse 메서드를 제공하여 문자열을 간단히 뒤집을 수 있다.

public static String reverse3(String word) {
   return new StringBuilder(word).reverse().toString();
}

 

동작 원리 

위의 코드는 StringBuilder 객체를 생성하고 입력된 문자열을 초기값으로 설정한다. StringBuilder 객체는 내부적으로 가변 크기의 문자열 버퍼를 가지고 있다. 그리고 reverse 메서드를 호출하여 문자열을 뒤집는데, 이때 문자열을 뒤집기 위해 버퍼 내의 문자들을 앞과 뒤에서부터 서로 교환한다. 첫 번째 문자와 마지막 문자, 두 번째 문자와 끝에서 두 번째 문자를 교환하는 식으로 문자열의 중앙까지 반복하여 교환 작업을 수행한다. 교환 작업이 완료되면 StringBuilder 객체는 뒤집힌 문자열을 가지게 된다.

마지막으로 toString 메서드를 호출하여 StringBuilder 객체의 내용을 문자열 형태로 변환하여 반환한다.

 

 

 

시간복잡도 

시간 복잡도는 입력된 문자열의 길이에 선형적으로 비례하며, O(N)이다.

 

 

장점

- 간단하고 직관적인 방법으로 문자열을 뒤집을 수 있다.
- 추가적인 메모리를 사용하지 않고 원본 문자열을 직접 수정하지 않는다.

 

 

단점 

- StringBuilder 객체를 생성하여 사용하기 때문에 메모리 사용량이 늘어날 수 있다.
- StringBuilder의 reverse 메서드는 문자열을 수정하기 위해 추가적인 연산을 수행하므로 상대적으로 느릴 수 있다.

 

 

4. 재귀 함수를 이용한 방법

 

마지막으로 재귀 함수를 사용하여 문자열을 뒤집을 수도 있다. 

 

public static String reverse4(String word) {
   if (word.isEmpty()) {
      return word;
   }

   return reverse4(word.substring(1)) + word.charAt(0);
}

 

동작 원리 

 

위의 코드는 재귀 함수인 reverse4를 정의한다. 함수 내부에서는 문자열이 비어있는지 확인한다. 만약 비어있다면, 즉 문자열의 길이가 0이라면 원래 문자열인 word를 그대로 반환한다. 문자열이 비어있지 않다면, word.substring(1)을 통해 첫 번째 문자를 제외한 나머지 부분을 얻는다. 이후 reverse4 함수를 재귀적으로 호출하여 나머지 부분을 뒤집은 결과를 얻는다. 이후 스스로를 재귀적으로 호출하여 나머지 부분을 뒤집은 결과를 얻는다. 재귀적으로 얻은 결과와 첫 번째 문자 word.charAt(0)를 연결하여 뒤집힌 문자열을 반환한다.

 

구체적으로 다음과 같다.  예를 들어, reverse4("Hello")를 반환하는 과정을 살펴보자. 

 

1) 함수 호출: reverse4("Hello") -> 문자열이 비어있지 않으므로, else 절로 이동.
2) 재귀 호출: reverse4("ello") -> 문자열이 비어있지 않으므로, else 절로 이동.
3) 재귀 호출: reverse4("llo") -> 문자열이 비어있지 않으므로, else 절로 이동.
4) 재귀 호출: reverse4("lo") -> 문자열이 비어있지 않으므로, else 절로 이동.
5) 재귀 호출: reverse4("o") -> 문자열이 비어있지 않으므로, else 절로 이동.
6) 재귀 호출: reverse4("") -> 문자열이 비어있으므로, if 절에 해당되어 빈 문자열 ""을 반환.
7) 역순 결합: "" + 'o'를 수행하여 "o"를 반환.

8) 역순 결합: "o" + 'l'을 수행하여 "ol"을 반환.
9) 역순 결합: "ol" + 'l'을 수행하여 "oll"을 반환.
10) 역순 결합: "oll" + 'e'를 수행하여 "olle"을 반환.
11) 역순 결합: "olle" + 'H'를 수행하여 "olleH"를 반환.

이와 같은 방식으로 재귀 함수를 사용하여 뒤집힌 문자열을 반환한다. 

 

 

시간복잡도 

 

재귀 호출이 문자열의 길이에 비례하여 수행된다. 따라서 입력된 문자열의 길이를 N이라고 할 때, 재귀 호출이 N번 수행되므로 시간 복잡도는 O(N)이다.

 

 

장점

 

- 구현이 간단하고 직관적이다.

(일반적으로 재귀는 직관적이지만 이 케이스에서는 return 부분이 쪼개져서 들어가기 때문에 조금 덜 직관적인 듯하다)
- 추가적인 메모리를 사용하지 않는다.

 

단점 

 

재귀 호출을 반복하므로 호출 스택의 깊이가 증가하게 되어 메모리 사용량이 증가할 수 있다.

 

 

 

 

결론 

 

모든 방법의 시간 복잡도는 O(n)으로 추가 조건이 주어지지 않는 한 이보다 좋은 효율(logn)로 replace()를 수행할 수 있는 방법은 존재하지 않을 것 같다.

 

각 방법에는 장단점이 있으며, 상황에 따라 가장 적합한 방법을 선택할 수 있다. StringBuilder를 사용하는 방법이 대부분의 경우 효율적이지만, 메모리 사용량이 중요한 상황이라면 배열과 스왑을 이용한 방법이나 재귀 함수를 사용하는 방법을 고려할 수 있을 것이다.

 

 

 

전체 코드 

 

package basic.string;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class Reverse {
   @Test
   public static void test() {
      Assertions.assertEquals(reverse("Hello"), "olleH");
      Assertions.assertEquals(reverse2("Hello"), "olleH");
      Assertions.assertEquals(reverse3("Hello"), "olleH");
      Assertions.assertEquals(reverse4("Hello"), "olleH");
   }

   public static void main(String[] args) {
      test();
   }

   /**
    * 주어진 문자열의 길이를 N이라고 할 때, for 루프를 통해 문자열을 역순으로 생성하는 과정이 수행된다.
    * 따라서 시간 복잡도는 O(N)
    *
    * StringBuilder를 사용하여 문자열을 구축한다. 이때 추가적인 메모리 사용이 필요하다.
    * @param word
    * @return
    */
   public static String reverse(String word) {
      StringBuilder stringBuilder = new StringBuilder();
      for (int i = word.length() - 1; i >= 0; i--) {
         stringBuilder.append(word.charAt(i));
      }

      return stringBuilder.toString();
   }

   /**
    * 이 방법은 문자열을 문자 배열로 변환하고, 배열의 시작과 끝 인덱스를 이용하여 문자를 교환하는 방식이다.
    * 시작 인덱스를 증가시키고 끝 인덱스를 감소시키면서 문자를 교환하며 반복한다.
    * 이를 통해 문자열이 역순으로 뒤집힌다.
    * 주어진 문자열을 직접 조작하므로 추가적인 메모리 사용은 없다.
    * 시간 복잡도는 O(N)
    * @param word
    * @return
    */
   public static String reverse2(String word) {
      char[] characters = word.toCharArray();
      int start = 0;
      int end = word.length() - 1;

      while (start < end) {
         swap(characters, start, end);
         start++;
         end--;
      }

      return new String(characters);
   }



   /**
    * StringBuilder의 reverse() 메서드를 사용하여 주어진 문자열을 역순으로 변환한다.
    * 시간 복잡도는 O(N)
    * 메서드 체인을 통해 간결하고 직관적인 코드를 작성할 수 있다는 장점이 있다.
    * @param word
    * @return
    */
   public static String reverse3(String word) {
      return new StringBuilder(word).reverse().toString();
   }

   /**
    * 재귀적인 방식을 사용하여 주어진 문자열을 역순으로 변환헌다.
    * 문자열의 길이를 N이라고 할 때, 재귀 호출이 N-1번 이루어지는 것을 볼 수 있다.
    * 시간 복잡도는 O(N)
    *
    * 재귀 호출을 통해 문자열을 역순으로 생성하므로 메모리 사용량은 증가하지 않는다.
    * 그러나 재귀 호출을 반복하면서 스택 공간을 사용하므로 깊은 재귀 호출이 발생할 경우 스택 오버플로우 가능성을 고려해야 한다.
    * @param word
    * @return
    */

   public static String reverse4(String word) {
      if (word.isEmpty()) {
         return word;
      }

      return reverse4(word.substring(1)) + word.charAt(0);
   }

   private static void swap(char[] characters, int start, int end) {
      char temp = characters[start];
      characters[start] = characters[end];
      characters[end] = temp;
   }


}