[백준 9012] 괄호 (stack)

• 안녕하세요. BlockDMask 입니다.

• 백준 알고리즘 사이트에서 단계별로 풀어보기를 하나하나 하고있습니다. ㅎㅎ

0. 제목

• 백준 9012 괄호

• BOJ 9012 괄호

1. 문제설명

괄호 문자열 (Parenthesis String, PS)는 '(', ')' 만으로 구성되어 있는 문자열을 말합니다.

흔히 우리가 말하는 소괄호.!

그 중 괄호의 모양이 바르게 구성된 올바른 괄호 문자열을 Valid PS, VPS라고 부릅니다.

"()" 는 VPS 입니다.

"()()(())" 는 VPS 입니다.

"())" 는 VPS 가 아닙니다.

처음 Test할 문자열의 갯수 N이 들어오고 

그다음 문자열이 N개 만큼 들어옵니다.

입력된 괄호 문자열이 올바른 괄호 문자열(VPS)이면 "YES"를 아니면 "NO"를 한줄에 하나씩 출력하시오.

2. 풀이과정

C++ STL 에서 지원해주는 stack 을 사용했습니다.

stack 을 사용하여 받은 문자열에서

[여는 괄호 일때] 

push

[닫는 괄호 일때]

1) 스택 내부에 여는 괄호가 있다. -> pop

2) 없다 -> false

[문자열을 다 확인했는데]

스택 내부에 여는 괄호가 있다 -> false

로 알고리즘을 구현했습니다.

3. 코드

//백준 9012번 괄호
 
#include<iostream>
#include<stack>
#include<string>
 
using namespace std;
 
bool Check(string str){
    int len = (int)str.length(); //문자열 길이
    stack<char> st;              //char 타입을 받는 stack 선언
 
    for(int i=0; i<len ; i++) { //문자열 길이만큼 반복문
        char c = str[i];        //문자 하나씩 받음
 
        if(c == '('){
            st.push(str[i]);    //여는 괄호면 push
        }else{
            if(!st.empty()){    //닫는 괄호면 stack 이 비어있는지 확인후
                st.pop();       //스택이 비어있지 않으면 pop
            }else{
                return false;   //비어있으면 false.
            }
        }
    }
 
    return st.empty();          //반복문이 끝나고 스택에 괄호가 남아있으면 false
}
 
int main(void){
 
    int n;
    cin >> n;
 
    for(int i=0; i<n; i++){
        string str;
        cin >> str;
 
        if(Check(str)){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
 
    return 0;
}

4. 인증

문제출처 - https://www.acmicpc.net/problem/9012

감사합니다. 한번 꾹 부탁드립니다.!