[백준 9012] 괄호 (stack활용)

https://www.acmicpc.net/problem/9012

9012번: 괄호

 

 

1. 문제 분석

정리하자면, 테스트 데이터로 '('와 ')'가 반복되는 랜덤한 배열이 주어지는데, 이것이 VPS인지 아닌지를 판단하는 문제!

그러면 어떤 경우에 VPS가 가능한건지 혹은 불가능 한것인지 예시를 통해 알아보자.

위의 예시들을 통해 VPS여부를 판단하는 두 가지 규칙을 확인할 수 있었는데,

첫 번째, 모든 과정이 종료된 이후, 짝을 짓지 못한 괄호가 한개라도 남아있으면 VPS가 아니다.

두 번째, 왼쪽 괄호는 반드시 오른쪽 괄호보다 먼저 등장해야 한다. 즉, 오른쪽 괄호만 먼저 등장했을 경우 이는 VPS가 아니다.

 

따라서 stack을 만들고, 왼쪽괄호가 등장할 경우 stack에 넣고 오른쪽 괄호가 등장할 경우 stack의 왼쪽 괄호를 하나 지운다. 이렇게 왼쪽 괄호를 지우면 짝이 된 괄호 쌍을 지우는 것을 의미한다.

위의 두가지 규칙을 반영하여  VPS 여부를 반별하는 if 조건문을 작성하면 될것이다.

 

2. 코드 작성하기

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int N;
    cin >> N;
    
    for (int i = 0; i < N; i++) {    //한줄단위 반복
        vector<char> v; //실제 입출력되는 stack
        string str;    
        cin >> str;
        
        for (int j = 0; j < str.length(); j++) {
            if (str[j] == '(') {
                v.push_back('(');
            }
            else if (str[j] == ')') {
                if (v.empty() == 1) {
                    cout << "NO" << endl;
                    break;
                }
                else {
                    v.pop_back();
                }
            }
            if (j == str.length() - 1) {
                if (v.empty() == 1)
                    cout << "YES" << endl;
                else
                    cout << "NO" << endl;
            }
        }
    }
 
    return 0;
}

string 형태로 괄호들을 입력받은뒤, str의 원소들에 대하여 str[j]로 하나씩 접근하여 VPS의 여부를 판별한다.

 

(c++의 string에 대해 까먹었더니,,, string 내의 글자들 하나씩에 대해 위와 같이 접근 할 수 있음을 몰라서

strcpy로 string을 char로 변환해서 접근하고.. 등등의 과정때문에 오히려 복잡했었다.

string 복습 좀 다시 해야겠다 ㅠ )