Java 솔루션: 중복 괄호 감지 O(N)

Source: Dev.to

문제

문자열 s 가 균형 잡힌 식을 나타낼 때, 그 안에 불필요한 괄호가 있는지 판단하라.
같은 부분식이 불필요하거나 중복된 괄호로 둘러싸여 있다면 그 괄호 쌍은 불필요한 것이다.

예시

• s = "((a+b))" → 불필요함
• s = "(a+(b)/c)" → 불필요하지 않음
• s = "(a+b+(c+d))" → 불필요하지 않음

제한조건: 1 ≤ |s| ≤ 10^5

비효율적인 접근법

1. 문자열을 순회하면서 여는 괄호 ( 를 찾는다.
2. 매칭되는 닫는 괄호 ) 를 찾기 위해 앞으로 스캔한다.
3. 그 사이의 부분 문자열을 추출한다.
4. 부분 문자열에 연산자(+, -, *, /)가 있는지 확인한다.
   • 연산자가 없으면 괄호는 불필요함(예: (a)).
   • 연산자가 있으면 중첩된 불필요한 괄호(((a+b)))를 세지 않도록 추가 검사가 필요하다.

이 방법은 같은 문자를 여러 번 스캔할 수 있어, 깊게 중첩된 괄호가 있을 경우 O(N²) 시간 복잡도가 발생한다.

스택을 이용한 O(N) 효율적인 해결법

식은 중첩 구조를 가지고 있으므로 후입선출(LIFO) 자료구조가 자연스럽게 맞는다. 문자들을 순차적으로 처리하면서 스택을 사용하면 한 번의 패스로 불필요한 괄호를 감지할 수 있다.

알고리즘

1. 빈 스택을 초기화한다.
2. 문자열의 각 문자 ch 를 순회한다:
   • ch 가 여는 괄호 ( 혹은 연산자(+, -, *, /)이면 스택에 푸시한다.
   • ch 가 닫는 괄호 ) 인 경우:
     1. 스택에서 여는 괄호 ( 가 나올 때까지 팝한다.
     2. 팝하면서 연산자가 등장했는지 확인한다.
        • 연산자가 하나도 없으면 현재 괄호 쌍은 불필요하므로 → true 반환.
     3. 매칭되는 ( 를 스택에서 제거한다.
3. 루프가 끝날 때까지 불필요한 괄호를 찾지 못하면 false 를 반환한다.

복잡도

• 시간: O(N) – 각 문자는 최대 한 번씩 푸시·팝된다.
• 공간: O(N) – 최악의 경우 스택에 식 전체 문자를 저장한다.

참고 구현 (Java)

import java.util.Stack;

class Solution {
    public static boolean checkRedundancy(String s) {
        if (s == null || s.isEmpty()) {
            return false;
        }

        Stack stack = new Stack<>();

        for (char ch : s.toCharArray()) {
            if (ch == ')') {
                boolean hasOperator = false;

                // Pop until the matching '('
                while (!stack.isEmpty() && stack.peek() != '(') {
                    char top = stack.pop();
                    if (isOperator(top)) {
                        hasOperator = true;
                    }
                }

                // Remove the '(' if present
                if (!stack.isEmpty()) {
                    stack.pop();
                }

                // No operator inside the parentheses → redundant
                if (!hasOperator) {
                    return true;
                }
            } else if (isOperator(ch) || ch == '(') {
                // Only push operators and '('; operands are irrelevant for redundancy check
                stack.push(ch);
            }
        }

        return false;
    }

    private static boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }
}

checkRedundancy 메서드는 입력 식에 불필요한 괄호가 하나라도 있으면 true를, 그렇지 않으면 false를 반환한다.