[백준] 9012번 : 괄호

문제

 

---

풀이

 

스택 문제에는 나혼자 정했지만 아마 일반화도 가능할 듯한 네임드 문제 2개가 있다. 후위표기법 사칙연산과 괄호 맞추기다.

유명한 문제들이니만큼 풀이법도 세뇌수준으로 들어서 툭 건드리면 툭 나올만큼 외웠다.

 

왼쪽 괄호가 나오면 스택에 넣고(push) 오른쪽 괄호가 나오면 pop하는데 pop을 하려할 때 이미 스택이 비어있거나, 문자열의 끝까지 탐색을 완료했는데 스택이 비어있지 않으면 올바른 괄호 문자열이 아니다.

 

자세한 설명을 원한다면...나보다 훨씬 잘 설명한 블로그가 정말 많다. 그만큼 유명한 문제라는 것이다.

---

소스코드

 

#include <iostream>
#include <stack>
#include <string>
using namespace std;

void bracket(string input, int length) {
    stack<int> s;

    for (int i = 0; i < length; i++) {
        if (input[i] == '(') //왼쪽 괄호면 push
            s.push(1);
        else if (input[i] == ')') { //오른쪽 괄호면 pop인데
            if (s.empty()) { //아무것도 없는데 pop 할 수 없음
                cout << "NO\n";
                return;
            }
            s.pop();
        }
    }
    if (s.empty()) //스택이 비어있으면 다 짝이 있었다는 뜻
        cout << "YES\n";
    else
        cout << "NO\n";
}

int main() {
    int n;
    string input;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> input;
        int length = input.size();
        bracket(input, length);
    }
}

굳이 int형 스택을 선언해서 push(1)을 한 건 그냥 별 이유없다.

char형 스택을 선언해서 괄호를 그대로 넣어도 되고 나처럼 해도 된다.