스택/큐 - 쇠막대기

https://www.welcomekakao.com/learn/courses/30/lessons/42585

 

위 문제를 푸는 로직은 다음과 같다.

 

1. 여는 괄호( '(' ) 는 레이저이든 막대이든 상관없이 스택에 넣는다.
2. 닫는 괄호( ')' )는 레이저이거나 막대기의 끝을 나타낸다. 그렇기 때문에 2가지로 로직으로 나뉠 수 있다.
    2-1. 바로 이전 괄호가 닫는괄호일 경우, 막대기를 나타내는 데 이 경우엔 막대기의 끝점을 나타내기 때문에 마지막에 잘린 부분을 정답에 더해준다. (18 line)
    2-2. 바로 이전 괄호가 닫는괄호가 아닌 경우 즉, 여는 괄호인 경우엔 레이저를 나타내므로 현재 스택에는 끝점을 만나지 않은 막대기들만 남아있으므로 스택의 크기만큼 정답에 더해준다. (19 line)

#include <string>
#include <vector>
#include <stack>
 
using namespace std;
 
int solution(string arrangement) {
    int answer = 0;
    
    stack<char> s;
    char cur, prev;
    
    for (int i = 0; i < arrangement.size(); ++i) {
        cur = arrangement[i];
        if (cur == ')') {
            s.pop();
            // 막대기의 끝일 땐 막대기 1개만 추가되며, 그 외는 stack 의 size 만큼 생김
            if (prev == ')') answer++;
            else answer += s.size();
        } else {
            s.push(cur);
        }
        prev = cur;
    }
    
    return answer;
}