[C++] 쇠막대기 (10799 번)

https://www.acmicpc.net/problem/10799

10799번: 쇠막대기

---

문제풀이

처음 문제를 딱 봤을 땐, 어 어려운데? 감이 잘 안오네 라는 생각을했다. 근데 왠지 모르게 본능적으로 스택을 써서 어떻게 하면 풀수 있을거란 생각이 났다. 문제를 많이 풀어보면서 생긴 느낌인가보다. 우선 레이저와 쇠막대기를 어떻게 구분할지 고민했는데, 이건 간단했다. 레이저는 바로 () 닫는 괄호가 나오고 쇠막대기는 그렇지 않다. 그렇다면 쇠막대기를 stack에 넣어주고, 레이저가 나온다면 두동강 나니까 stack 에 들어있는 개수만큼의 쇠막대기가 모두 두동강 나서 두배로 늘어난다고 생각했다.

 

다시 설명하자면,

1. 여는 괄호가 나올 때, 바로 닫는괄호가 나오는지 확인하여 레이저인지 쇠막대기인지 구분한다.

2. 쇠막대기라면, stack에 넣어준다. 그리고 정답, 즉 쇠막대기 개수를 하나 증가시켜 준다.

3. 레이저라면, 현재 stack에 들어가 있는 쇠막대기 개수만큼을 정답에 더해준다. 모두 두동강 나버리기 때문이다.

4. 닫는 괄호를 만나면 stack 에 있는 쇠막대기를 하나 빼준다.

 

이런 절차로 구현하면 되겠다고 생각했다. 코드는 짧다. 풀이법을 생각하고 나니 10분만에 풀어버렸다. 하하

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    stack<int> st;
    string s;
    cin >> s;

    int answer = 0;
    for(int i=0; i<s.size(); i++) {
        if(s[i] == '(') {
            if(s[i+1] == ')') {
                i++;
                answer += st.size();
            }
            else {
                answer += 1;
                st.push(1);
            }
        }
        else {
            st.pop();
        }
    }
    cout << answer;
    return 0;
}