괄호

문제

괄호

풀이

문자열을 왼쪽부터 오른쪽으로 하나씩 살펴보면서 만약 ”(” 이라면 스택에 넣고, ”)“이라면 스택에서 하나를 뺍니다. 스택이 비어있어서 뺄 수 없다면 VPS가 아닙니다. 또한 위 과정이 전부 끝나고 나서 스택에 문자가 남아있으면 VPS가 아닙니다.

직접 스택에 넣는 것 대신 열린 괄호의 개수를 세는 방식으로 해도 풀 수 있습니다. 원리는 같습니다.

코드

Python

def solve():
    s = input()
    stack = []
    for i in s:
        if i == ")":
            if stack:
                stack.pop()
            else:
                print("NO")
                return
        else:
            stack.append(i)
    print("NO" if stack else "YES")
 
 
for _ in range(int(input())):
    solve()

C++

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    string s;
    cin >> s;
 
    stack<int> st;
    for (char i : s) {
        if (i == ')') {
            if (not st.empty())
                st.pop();
            else {
                cout << "NO\n";
                return;
            }
        } else
            st.push(i);
    }
    cout << (st.empty() ? "YES" : "NO") << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t--)
        solve();
 
    return 0;
}

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
 
public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
 
    public static void solve() throws IOException {
        String s = br.readLine();
        Stack<Character> stack = new Stack<>();
 
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (!stack.empty())
                    stack.pop();
                else {
                    bw.write("NO\n");
                    return;
                }
            } else
                stack.add(s.charAt(i));
        }
        bw.write(stack.empty() ? "YES" : "NO");
        bw.write('\n');
    }
 
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++)
            solve();
        
        bw.close();
    }
}
``