이번에는 자바에서 스택(Stack)을 이용하여 문자열을 뒤집는 알고리즘을 구현해보겠습니다.

알고리즘 개요

먼저, 스택은 후입선출(LIFO - Last In, First Out)의 자료구조로, 데이터를 한쪽 끝에서만 접근할 수 있는 구조입니다. 문자열을 뒤집기 위해서는 문자열을 한 글자씩 스택에 넣은 뒤, 스택에서 역순으로 꺼내면 됩니다.

구현 방법

이제 실제로 코드를 구현해보겠습니다.

import java.util.Stack;

public class StringReversal {
    public static String reverseString(String input) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < input.length(); i++) {
            stack.push(input.charAt(i));
        }

        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

        return result.toString();
    }

    public static void main(String[] args) {
        String input = "Hello, World!";
        String reversed = reverseString(input);
        System.out.println("Reversed string: " + reversed);
    }
}

동작 설명

위 코드에서는 reverseString 메소드를 통해 문자열을 뒤집습니다. 먼저, 입력된 문자열을 순회하면서 각 문자를 스택에 넣습니다. 그리고 스택이 비어있지 않을 때까지 스택에서 문자를 꺼내 결과 문자열에 추가합니다. 이렇게 하면 입력된 문자열의 순서가 역순으로 뒤집힌 문자열이 생성됩니다.

위의 예시 코드는 “Hello, World!”라는 문자열을 뒤집어 “dlroW ,olleH”라는 결과를 출력합니다.

시간 복잡도

위 알고리즘의 시간 복잡도는 O(n)입니다. 문자열의 길이가 n일 때, 각 문자를 스택에 넣는 과정과 스택에서 문자를 꺼내는 과정은 모두 O(1)이므로, 전체적인 시간 복잡도는 O(n)이 됩니다.

결론

스택을 이용한 문자열 뒤집기 알고리즘을 자바로 구현하는 방법을 알아보았습니다. 스택의 특성을 이용하여 문자열을 역순으로 생성하는 방법을 알고 있다면, 다양한 문자열 처리 문제에 응용할 수 있습니다.