[백준 9012번 C++] 괄호

9012번: 괄호 (acmicpc.net)

9012번: 괄호

괄호 문제는 스택의 가장 대표적인 유형

 

문제의 나의 코드

첫번째 input은 잘 되는 데, 두번째부터는 input이 이상하게 들어가짐

 

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

using namespace std;

int main()
{
    int n;
    string input;
    stack<char> s;
    
    cin >> n; 
    
    for(int i=0; i<n; i++){
        cin >> input;
        while( !s.empty() ) s.pop();
        for(int j=0; j<input.length(); j++){
            if(input[j] == '(') {
                s.push('(');
                cout<< "push '('  ";
            }
            
            else if(input[j] == ')') {
                if(s.empty()){
                    s.push(')');
                    cout << "push '('  ";
                    cout <<"NO\n";
                    break;
                }
                
                else{
                   s.pop(); 
                   cout << "pop ')'  ";
                } 
            }
            
        }
        if(s.empty()) cout << "YES\n";
        
    }

    return 0;
    
}

출력하면

push '('  push '('  pop ')'  pop ')'  push '('  pop ')'  push '('  NO
push '('  push '('  push '('  push '('  pop ')'  push '('  pop ')'  pop ')'  push '('  pop ')'  push '('  push '('  pop ')'  push '('  pop ')'  pop ')'  push '('  push '('  push '('  pop ')'  pop ')'  pop ')'  YES
push '('  push '('  push '('  pop ')'  push '('  pop ')'  push '('  push '('  pop ')'  pop ')'  pop ')'  push '('  push '('  push '('  push '('  pop ')'  pop ')'  pop ')'  pop ')'  push '('  pop ')'  push '('  pop ')'  push '('  pop ')'  push '('  pop ')'  push '('  pop ')'  push '('  push '('  pop ')'  push '('  pop ')'  push '('  pop ')'  pop ')'  push '('  pop ')'  YES
push '('  push '('  pop ')'  push '('  push '('  push '('  pop ')'  pop ')'  push '('  pop ')'  push '('  

이렇게 나온다

 

[C++][백준 9012][스택] 괄호 :: seoftware (tistory.com)

[C++][백준 9012][스택] 괄호 :: seoftware

아래처럼 수정을 해줬는데, 

) 가 나왔을 때, pop하는 조건이

 if(!s.empty() && s.top() == '(') 이어야 한다. 

기존에는 그냥 !s.empty()로 해줬는데 top=='('인지도 검사해야 함

for(int j=0; j<input.length(); j++){
            if(input[j] == '(') {
                s.push(input[j]);
            }
            
            else if(input[j] == ')') {
                if(!s.empty() && s.top() == '('){
                    s.pop();
                }
                
                else{
                   answer = "NO";
                   break;
                } 
            }
        }

 

그렇게 나온 최종 코드는

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

using namespace std;

int main()
{
    int n;
    string input;
    stack<char> s;
    
    cin >> n; 
    
    for(int i=0; i<n; i++){
        cin >> input;
        string answer = "YES";
        
        while( !s.empty() ) s.pop();
        
        for(int j=0; j<input.length(); j++){
            if(input[j] == '(') {
                s.push(input[j]);
            }
            
            else if(input[j] == ')') {
                if(!s.empty() && s.top() == '('){
                    s.pop();
                }
                
                else{
                   answer = "NO";
                   break;
                } 
            }
        }
        if (!s.empty()) answer = "NO";
    
        cout << answer << "\n";
    }

    return 0;
    
}