스택_백준_괄호_9012

닫는 괄호 입장

1. 여는 괄호가 왼쪽에 조재

2. 짝이 없는 여는 괄호중에 선택

3. 가장 오른쪽 여는 괄호 선택

우선 가장 생각하기 쉬운 방법은 처음부터 끝까지 for문으로 탐색을 하면서 동시에 자신보다 왼쪽에 있는것들중에서 짝이 없는 괄호를 선택하는 것이다.

하지만 이는 O(N^2)으로 시간 초과가 뜬다.

3번 조건을 보면 가장 오른쪽 것을 선택한다. 즉 이는 top을 의미하며 이 문제는 stack을 이용해서 풀어야 한다.

처음부터 끝까지 탐색을 하면서 stack에 push/pop을 하므로 시간복잡도는 O(N)이다.

풀이1

#include <iostream>
#include <stack>
#include <string>
using namespace std;
 
int main() {
    string input;
    int count;
    cin >> count;
 
    for (int i = 0; i < count; i++) {
        cin >> input;
        stack <char> s;
 
        for (int j = 0; j < input.size(); j++) {parenthesis only
            if (input[j] == '('){
                s.push('(');
            }  // Only open parentheses are pushed onto the stack.
            else {
                if (s.empty()) {
                    s.push('('); // Not overlap 29 Line
                    break;
                } // When the closing parenthesis comes first
                else {
                    s.pop();
                }
            }
        }
        if (s.empty()) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        } // When there are more open parentheses
    }
 
    return 0;
}

풀이2

#include <iostream>
#include <string>
using namespace std;
 
int main() {
    string input;
    int count = 0;
    int result;
    cin >> count;
 
    for (int i = 0; i < count; i++) {
        cin >> input;
        result = 0;
        for (int i = 0; i < input.size(); i++) {
            if (input[i] == '(') {
                result++;
            }
            else {
                if (result == 0) {
                    result = -1;
                    break;
                }
                result--;
            }
        }
        if (result != 0) {
            cout << "NO" << endl;
        }
        else {
            cout << "YES" << endl;
        }
    }
    return 0;
}
// The stack size is important, not the stack value.