[프로그래머스] 스택/큐 - 쇠막대기, C++

https://programmers.co.kr/learn/courses/30/lessons/42585

코딩테스트 연습 - 쇠막대기 | 프로그래머스

 본 문제는 2015 한국정보올림피아드 지역본선 초등부 3번, 중등부 2번 문제로 프로그래머스와 백준 10799번 쇠막대기와 동일한 문제다. 개인적으로 글로만 문제를 이해하기가 어려웠다. 따라서, 사진을 통해 설명하도록 한다.

<쇠막대기 사진>

 사진의 좌측과 우측이 문제해결의 가장 큰 힌트라고 생각된다.  우선 좌측을 보면 '( )' 입력 시 레이저가 작동한다. 그리고 우측에는 '( ( ) )' 입력이 들어왔고, 결과는 쇠막대기가 2개로 잘렸다. 문제를 좀 더 자세히 해석하면 '( (' 입력에는 아무런 반응을 하지 않고 ')' 입력 시, 이전 입력이 '('의 여부에 따라 쇠막대기가 추가되는 개수가 결정된다. 예를들어 '( ( ( ( ( ( )' 와 같은 입력이 들어왔다고 하자. ')' 입력이 들어왔을 때 이전 입력이 '(' 이기 때문에 레이저는 작동하게 되고, 작동했을 때 '(' 의 개수가 6개 이므로 5개의 쇠막대기를 추가하면 된다. 그렇다면 ')' 입력이 들어왔을 때, 이전 입력이 '('가 아닐 경우는 어떻게 처리하면 좋을까? 정답은 쇠막대기 한 개를 추가하면된다. 결과적으로 stack을 사용했을 시, 다음과 같은 과정이 도출된다.

1. '(' 입력 시, stack에 push
2. ')' 입력 시, 이전 입력이 '(' 이면 stack을 pop하고, stack의 길이 만큼 추가.
3. ')' 입력 시, 이전 입력이 '(' 이 아니면 stack을 pop하고, 한 개 추가

#include <string>
#include <vector>
#include <stack>
 
using namespace std;
 
int solution(string arrangement) {
    int answer = 0;
    int num = arrangement.size();
    stack<int> s;
    for (int i = 0; i < num; i++) {
        if (arrangement[i] == '(') s.push(i);
        // ')' 입력 시 이전 입력이 '(' 인지 확인
        else {
            // 맞을 경우
            if (s.top() == i-1) {
                s.pop();
                answer += s.size();
            }
            // 아닐 경우
            else {
                s.pop();
                answer += 1;
            }
        }
    }
    return answer;
}