올바른 괄호 - 프로그래머스, c++

 

 

괄호 검사 문제는 스택을 사용해야 한다.

(괄호의 종류가 "(", "{", "[" 중 얼마나 있냐에 따라 코드의 내용은 조금씩 달라지지만 전체적인 틀은 같다.)

왼쪽 괄호는 스택에 들어가는 역할을 하고

오른쪽 괄호일 경우 왼쪽 괄호가 스택안에 있냐 없냐를 체크하고 상황에 맞게 스택 안의 왼쪽 괄호를 pop 해주면 된다.

 

 

- 문제 풀이

1. 문자열 s 길이만큼 for문을 돌며 "(", ")"에 따라 스택을 사용한다.

2. for문 안에서

          → 만약 현재 인덱스가 가르키는 문자가 "(" 라면 스택에 넣는다.

          → 만약 현재 인덱스가 가르키는 문자가 ")" 라면 스택 안의 상황을 보고 스택 안의 "("를 pop한다.

 

 

- 코드

다음과 같이 간단하게 구현하여 성공했다.

(+ 스택 선언 하는 방법: stack<int> s;)

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

using namespace std;

bool solution(string s)
{
    bool answer = true;

    stack<char> stack;
    
    for(int i=0; i<s.length(); i++) {
        
        // 왼쪽 괄호를 만나는 경우 stack에 push
        if(s[i]=='('){
            stack.push(s[i]);
        }
        
        // 오른쪽 괄호를 만나는 경우 stack의 top과 비교
        if(s[i]==')'){
            if(stack.empty()){
                answer = false;  // stack이 비어있는 경우 false
                break;
            }
            else{
                stack.pop();    // stack의 "("를 pop
            }
        }
    
        if( i == s.length()-1 && !(stack.empty()) )  {
            answer = false;
        }
    }
    
    return answer;
}