백준 10799: 쇠막대기

문제

이 문제는 스택을 이용하여 푸는 문제이다. 

문제의 핵심은 ')'를 만났을 때 레이저인지 막대기의 끝인지 구별해 내는 것이다.

먼저 '('를 만났을 때는 스택에 push를 해준다. 

')' 를 만났을 때는 스택에서 pop을 해준다.  

')'은 막대기의 끝을 나타낼 수도 있고, 레이저를 나타낼 수도 있다.

이 2가지의 경우를 나누는 방법은 레이저는 바로 직전의 문자가 '('이라는 것이다. 

따라서 이전의 문자를 보면서 이 둘을 구별할 수 있다.

잘려진 막대기의 개수를 구하는 방법은 레이저를 만났을 때는 스택에 쌓여있는 '('의 개수만큼 더해주고, 

막대기의 끝을 만났을때는 1만큼만 더해준다.

레이저를 만났을 때 막대기가 몇개가 있는가에 따라서 잘려나간 막대기의 수가 정해지며, 막대기의 끝을 만났을 때에는 해당 막대기만 끝이 났기 때문에 1만 더해주면 되는것이다. 

예제를 보면, 처음에는 '('가 나온다. 이때는 스택에 저장을 해준다.

그 뒤로 바로 ')'가 나오므로 스택에서 pop을 한다. 이전에 문자가 '('이므로 레이저를 뜻하게 된다. 이때는 막대기가 없으므로 결과에는   0이 더해지게 된다.

다음으로는 연속으로 '('이 4개가 나오게 되는데 모두 push를 해준다.

다음에는 ')'이므로 pop을 하고, 이전의 문자가 '('이기 때문에 레이저를 뜻한다. 현재 스택에 '('이 3개가 저장되어 있으므로 나무막대기가 3개가 겹쳐져 있다는것을 알 수 있다. 따라서 결과값에 스택에 저장되어있는 '('의 수만큼 더해준다. 

결과값에는 3을 더해 현재 결과값은 3이된다.

다음 문자에는 ')'가 나오고 이전과 같이 pop을 시켜준다. 이전의 문자가 '('이 아니기 때문에 이는 나무토막의 끝인것을 알 수 있다.

따라서 결과값에 1을 더해 4가된다.

이러한 방식으로 계속해서 하다보면 답이 나오게 된다.

코드

#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
int main(){
    string input;
    stack<char> s;
    int result = 0;
    
    cin >> input;
    
    for(int i = 0; i < input.size(); i++)
    {
        //'(' 일 경우에는 스택에 넣어준다.
        if(input[i] == '(')
            s.push(input[i]);
        //')' 일 경우에는 스택에서 빼준다.
        else{
            s.pop();
            //레이저일 경우
            if(input[i-1] == '(')
                result += s.size(); //스택의 사이즈만큼 더해준다.
            //막대기의 끝일 경우
            else
                result += 1;    //1을 더해준다.
        }
    }
    cout << result << endl;
    return 0;
}