[C++] 백준 알고리즘 9012번 (괄호)

문제

 

 

---

이번에 다뤄볼 문제는 9012번 문제 '괄호'입니다.

괄호문제에서 연습해야 하는 key-point는 스택입니다

 

스택은 선입후출 방식의 자료구조인데요, 가장 먼저 들어온 값이 가장 마지막에 빠지는 구조라고 생각하시면 됩니다.

예를들어 우리가 원통 기둥안에 물건을 하나씩 쌓아서 넣은뒤 그걸 다시 꺼내려면 가장 마지막에 넣었던 물건부터 꺼내게 되는데 이걸 스택이라고 합니다.

 

이 문제에서 스택을 사용할때는 "top"이라는 변수를 활용하겠습니다.

top변수는 스택으로 사용할 배열에서 현재 어느 위치까지 값이 들어갔는지 어느 위치까지 값을 꺼내왔는지를 알기위한 일종의 Index라고 생각하면 됩니다. 

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

 

코드(C++)

#include<iostream>
#include<string>
using namespace std;
 
int main() {
 
    char stack[51];
    string str;
    int empty = 0;
    int n;
    int top = -1;
 
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        cin >> str;
        for (int i = 0; i < (int)str.length(); i++) {
            if (str.at(i) == '(') stack[++top]= str.at(i);
            else {
                if (top == -1) {
                    empty = 1;
                }
                else stack[top--];
            }
        }
        if (top == -1 && empty == 0) cout << "YES" << endl;
        else cout << "NO" << endl;
        empty = 0;
        top = -1;
    }
    return 0;
}

9012번: 괄호