[백준] 10799 | 쇠막대기 | C++

풀이의 핵심은 이렇다.

 

입력으로 주어진 문자열을 하나씩 순서대로 처리한다:
    만약 ( 이라면:
        막대기의 시작을 알리는 것이다.
        stack에 넣는다;
    만약 ) 이라면:
    	stack pop;
        stack의 top(가장 최근에 넣은 값)이 ( 이라면:
            레이저로 인해 조각들이 생겼다.
            생겨난 조각 수(stack의 size)만큼 결과값에 더한다;
        stack의 top(가장 최근에 넣은 값)이 ) 이라면:
            조각의 끝을 알리는 것이다.
            결과값에 하나를 더한다;

 

위의 그림과 함께 보면

의사코드의 이해에 도움이 될 것이다.

 

주의할 점은,

) 을 처리하려는데

이전에 ( 이 들어왔다면,

막대기가 아닌 레이저이므로 미리 stack에서 pop시켜야 한다.

그래야 조각 수를 올바르게 더할 수 있다.

 

) 을 처리하려는데 이전에도 ) 이 들어왔다면,

어차피 조각(혹은 막대기)을 빼내야 하니

stack에서 pop시키는 것은 공통된 연산이다.

 

(중요한 것은 pop시키는 순서이다.)

 

---

 

정답 소스코드

 

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    int res=0, laser=0;
    string inp;
    stack<char> stk;
    cin>>inp;
    for(int i=0; i<inp.size(); i++) {
        if(inp[i]=='(') stk.push('(');
        else {
            stk.pop();
            if(inp[i-1]=='(') res+=stk.size();
            else res++;
        }
    }
    cout<<res<<"\n";
    return 0;
}

 

---

 

풀 때는 별의별 생각이 다 들어서 어려웠다.

막대기를 pop시키는 시점에 조각을 더하는 줄 알았다.

그래서 밑의 막대기는 또 어떻게 처리해야하나 싶었는데,

막상 다른 사람들의 풀이를 보니 레이저로 절단한 시점에 더하는 것이었다.