[java] 스택을 이용한 알고리즘의 최적화 방법 알아보기

05 Dec 2023

java

알고리즘을 개발하다보면 효율적인 처리를 위해 최적화가 필요한 경우가 많습니다. 스택을 사용하여 알고리즘을 최적화하는 방법을 알아보겠습니다.

스택(Stack) 이란?

스택은 후입선출(LIFO - Last In First Out) 원칙에 따라 동작하는 자료구조입니다. 즉, 가장 나중에 삽입된 항목이 가장 먼저 삭제되는 구조를 가지고 있습니다.

스택을 활용한 알고리즘 최적화

스택은 여러 알고리즘에서 활용될 수 있으며, 특히 다음과 같은 경우에 최적화에 유용합니다.

1. 괄호 검사

괄호 검사는 주어진 문자열에서 괄호의 유효성을 확인하는 작업입니다. 스택은 여는 괄호(‘(‘ 나 ‘[‘)를 만나면 스택에 넣어두고, 닫는 괄호 (‘)’ 나 ‘]’)를 만나면 스택의 top 항목과 대응되는지 확인하여 유효성을 판단할 수 있습니다.

import java.util.Stack;

public class BracketChecker {
    public static boolean isValid(String input) {
        Stack<Character> stack = new Stack<>();

        for (char c : input.toCharArray()) {
            if (c == '(' || c == '[') {
                stack.push(c);
            } else if (c == ')' || c == ']') {
                if (stack.isEmpty()) {
                    return false;
                }

                char top = stack.pop();
                if ((c == ')' && top != '(') || (c == ']' && top != '[')) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

2. 함수 호출 스택 추적

재귀 함수나 함수 호출 등에서 함수의 호출 순서를 추적해야 할 때 스택을 이용할 수 있습니다. 각 함수 호출 시 스택에 함수 정보를 저장하고, 함수의 종료 시 해당 정보를 스택에서 제거함으로써 호출 순서를 추적할 수 있습니다.

3. 뒤집기 연산

뒤집기 연산은 주어진 데이터를 역순으로 만드는 작업입니다. 예를 들어, 문자열을 뒤집을 때 스택을 사용할 수 있습니다. 문자를 순서대로 스택에 저장한 뒤, 스택에서 꺼내어 역순으로 만들 수 있습니다.

import java.util.Stack;

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

        for (char c : input.toCharArray()) {
            stack.push(c);
        }

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

        return sb.toString();
    }
}

정리

스택은 여러 알고리즘에서 유용하게 활용되는 자료구조입니다. 괄호 검사, 함수 호출 추적, 뒤집기 연산 등에서 스택을 적절히 이용하면 알고리즘의 효율성을 높일 수 있습니다. 주어진 문제나 상황에 따라 스택을 적절히 활용하는 것이 중요합니다.

참고 자료: