[백준 9012번] 괄호 (C++)

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

9012번: 괄호

 

이번 포스팅에서는 백준 9012번 문제를 학습합니다.

 

 

 

 

이번 문제도 스택 라이브러리를 이용해서 풀 수 있고, 직접 구현해서도 풀 수 있다.

 

1. 직접 구현

#include <iostream>
#include <string>

using namespace std;


int main(){
    int T;
    cin>>T;
    string str;
    
    for(int i=0; i<T; i++){
        cin>>str;
        int k=0;
        for(int j=0; j< str.length(); j++){
            if(str[j]=='('){
                k++;            }
            else {
                k--;
            }
            if(k<0){
                break;
            }
            
        }
        if (k == 0){
            cout<<"YES"<<"\n";
           
        }
        else {
            cout<<"NO"<<"\n";
       
        }
    }
    return 0;
}

먼저 입력 데이터의 수T를 입력받는다.
그 다음 for문 안에서 str을 입력 받는다.

str 문자 하나 하나를 살펴 봐야하므로 str 문자 길이 만큼의 for문을 만든다.

이 for문 안에서 '(' 가 있다면 k의 값을 증가하고, 그렇지 않다면( ')' 또는 다른 문자) k의 의 값을 뺀다. 만약 k가 0보다 작으면 for 문을 나온 후 NO를 출력한다.

만약 k가 0보다 작지 않다면 str의 길이 만큼 for문을 돈 다음 '(' 와 ')' 의 개수가 같아 k값이 상쇄되어 0이 된다면 YES를 출력한다.

 

2. STL Stack 라이브러리 사용

#include <iostream>
#include <string>
#include <stack>

using namespace std;
int main(){
    string str;
    int T;
    stack<char> st;
    
    cin>>T;
    for(int i=0;i<T;i++){
        int k=0;
        cin>>str;
        for(int j=0; j< str.length();j++){
            if(str[j]=='('){
                st.push(str[i]);
            }
            else{
                if(!st.empty()){
                    st.pop();
                }
                else{
                    k++;
                }
            }
        }
            if (k!=0){
                cout<<"NO"<<"\n";
            }
            else if(!st.empty()) {
                cout<<"NO"<<"\n";
            }
            else {
                cout<<"YES"<<"\n";
            }
        while(!st.empty()){
            st.pop();
        }
        
    }
}

우선 stack 라이브러리를 include 해준다.

그 다음 입력데이터 수T를 입력 받는다.

for문 안에서 k를 0으로 초기화 해준다. str을 입력 받는다.

( 입력 받은 문자의 길이만큼 반복하는 다음 for문에서 '('를 입력 받았다면 스택에 저장 후, ')'를 입력 받을 때 마다 스택에서 '('를 제거한다. 그러므로 stack인 st가 차있다면 k값이 양수이고, 비어 있다면 0이 될 것이다.)

따라서 k값이 0이 아니라면 NO 를 출력한다.

그리고, stack st가 차있다면 NO를 출력한다.

그렇지 않다면 YES를 출력한다.

이제 다음 string을 입력받기위해 주어진 stack 를 초기화 해준 후 for문을 반복 진행한다.

 

 

 

 

 

 

*유의사항

- 공부 중인 인공지능공학과 대학생이 정리해서 남긴 정리입니다.

- 정확하지 않거나, 틀린 점이 있다면 댓글로 알려주시면 감사하겠습니다.