JArchive 프로그래밍 일기

쇠막대기

문제링크

스택/큐 를 주제로 많은 사람들이 풀어보는 쇠막대기 문제다. (프로그래머스 level 2)

리뷰

괄호가 레이저 또는 막대를 표현한다.

그래서 여는 괄호와 닫는 괄호의 짝이 맞고 반드시 여는 괄호부터 시작된다.

여는괄호와 닫는괄호가 연속한 것을 레이저로 인식하도록 했다. 그래서 open_flag를 두었다.

레이저가 아니고서야 닫는괄호가 나오면 막대의 끝인 것이다.

레이저가 끝나면 스택에 있는 여는괄호 수 만큼 더해준다.

막대가 끝나면 막대하나가 끝난 거니까 +1 해준다.

#include <string>
#include <vector>
#include <stack>
using namespace std;


int solution(string arrangement) {

    int answer = 0;
    int i, len = 0;
    stack<char> st;
    bool open_flag = true;

    len = arrangement.size();

    for(i=0; i<len; i++){
        // printf("%c\n", arrangement[i]);
        char pa = arrangement[i];

        if(pa == '(') { // 여는 괄호라면  
            st.push(pa);
            open_flag = true;

        }else{ // ')' 닫는 괄호라면  
            st.pop();
            if(open_flag){ // 레이저  
                answer += st.size();
            }else{
                answer++;
            }
            open_flag = false;


        }
    }

    return answer;
}