스터디 1일차_[백준9012 괄호]

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

9012번: 괄호

스택을 이용해서 괄호문제를 풀어봤습니다.

 

긴 원통형같은 자료구조를이용해서

괄호 문자열을 받아주고 각각 한 글자씩 확인해 나가면서

1. '(' 이면 '('을 스택에 넣고

2. ')'이면 '('을 스택에서 빼는

 

동작을 이용해서 풀어봤습니다.

 

저기서

')' 이면 ')'을 빼는게 아니라

'('을 빼야되는거 조심해주세요.

 

한 쌍의 괄호 기호로 된 “( )” 문자열.

'(' 가 있으면 ')' 도 있다 라는것을.

넣기와 빼기 의동작의 기호라고. 생각하고.

넣고 빼는 동작수가 균형을 이루게 (동작수가 같게) 만들어준다면.

괄호 문자열이 VPS이 될것입니다.

 

단...

 

동작수가 같다고 무조건 VPS가 되는건 아닙니다.

예시로 " ) ) ) ( ( ( " 이건 VPS 가 아니죠.

 

그래서 '(' 가 없는데 ')' 가 나온다는것

즉 '(' 넣지도 않았는데 '('빼는 동작은 제외시킵니다.

"문자열이 끝나지 않았는데" 라는건...

입력한 괄호문자열 한 글자씩 모두 확인도 안해준 상황을 말합니다.

 

[ 괄호문자열 처음부터 끝까지 모두 

'('   ')' 확인해보지도 않았는데 == (넣고 뺴는 동작이 끝나지도 않았는데) ]

아래 같은 상황은 '(' ')'개수가 균형을 이루지 못한 상황이라서

VPS 가 아닙니다.

 

즉 넣고 빼는 동작에서 넣는 동작보다 빼는 동작이 부족해

비어있지 않고 뭔가 아직 남아있는 상황을 말하죠.

 

#include <iostream>
#include <stack>    //스텍 헤더
#include <string>    //문자열 
using namespace std;
int N;                //테스트 케이스
stack<char> st;        //스텍 생성
bool is_fail;        //괄호 문자열 VPS의 / NO, YES 판별
string str;            //받아줄 주어진 괄호 문자열 VPS 
//////////////////////////////////
int main()
{
    cin >> N;
    while (N--)        //테스트 N 개만큼 반복
    {
        cin >> str;    //괄호 문자열 받아주기
        int k = 0;    //괄호 문자열 길이만큼 반복하게끔 + 괄호문자열 k 번째 위치(인덱스) 가져오기    
 
    ///////////////////////////////// 
        do
        {
            if (str[k] == '(')        // '('이면  '(' 스텍에 넣는 동작
                st.push(k);
            else if (str[k] == ')') // ')' 가 들어왔으면...
            {
                if (st.empty())        //아직 괄호 문자열 끝까지 가져오기도 전에 비어있으면..
                {
                    is_fail = true; //(VPS 실패한것이 참)
                    break;
                }
                st.pop();            // ')'이면 [스텍에 들어가있는 ')'] 을 빼는 동작
            }
            k++;
        } while (k != str.size());    // [ 괄호 문자열 크기 = str.size() ] 만큼 반복
 
    ////////////////////////////////// 스텍에 뭔가 남아있을때 (VPS 실패한것이 참)
        if (!st.empty())
            is_fail = true;
    ///////////////////////////////// 출력물
        if (!is_fail)
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
    ///////////////////////////////// 
        while (!st.empty()) //스텍 비우기
            st.pop();
 
        is_fail = false;//VPS 실패한것이 거짓 (VPS 실패 안함) 초기화
        str.clear(); //괄호문자열 초기화
    }
}

9012번: 괄호