[Programmers] #12909 - 올바른 괄호 [Java][C++][Python]

문제 링크

---

1. 아이디어

여는 괄호와 닫는 괄호는 항상 가장 최근에 열린 괄호와 먼저 짝을 맞춰야 하므로, 스택으로 열린 괄호를 추적하면 자연스럽게 처리된다. 여는 괄호를 만나면 스택에 쌓고, 닫는 괄호를 만나면 스택에서 하나를 꺼내 짝을 지운다. 이때 짝지을 여는 괄호가 없는데 닫는 괄호가 나오면(스택이 비어 있으면) 그 시점에 이미 올바르지 않은 괄호이므로 바로 false를 반환한다. 문자열을 끝까지 순회했는데도 스택이 비어 있다면 모든 괄호가 짝을 이뤘다는 뜻이므로 올바른 괄호다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = 문자열 s의 길이)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    boolean solution(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                stack.pop();
            }
        }

        return stack.isEmpty();
    }
}

#include <bits/stdc++.h>
using namespace std;

bool solution(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            st.pop();
        }
    }

    return st.empty();
}

def solution(s):
    stack = []

    for c in s:
        if c == "(":
            stack.append(c)
        else:
            if not stack:
                return False
            stack.pop()

    return not stack

---

참고

괄호 종류가 여는/닫는 하나뿐이라 스택 없이 정수 카운터만으로도 $O(1)$ 공간에 판별할 수 있다. (를 만나면 카운터를 증가시키고 )를 만나면 감소시키되, 그 순간 카운터가 음수가 되면 그 즉시 false를 반환한다. 끝까지 순회한 뒤 카운터가 0이면 올바른 괄호 문자열이다.

---