[백준 10799] 쇠막대기 문제

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

다음 문제는 레이저로 쇠막대기를 자르는 문제였다.

인접한 한 쌍인 () 괄호 한 쌍는 레이저를 나타내고 떨어져있는 () 괄호 한 쌍은 쇠막대기를 의미한다.

그림으로 파악하자면 다음과 같다. 지난글 문제와 비슷하게 괄호의 쌍을 찾는 부분은 비슷하기 때문에 스택을 이용하기로 했다.

지난글 문제 : 2018/03/28 - [백준 문제풀이] - [9012] 괄호 문제

처음 내가 시도했을 때 이론은 비슷했다.

'(' 하나가 나올때마다 스택에 push 했으며 인접한 괄호 한쌍 즉 레이저가 나왔을때는 스택에 레이저의 괄호를 제외한 나머지 막대기 부분의 '(' 개수를 sum에 더하여 잘린 막대기 수를 더했고 레이저가 아닌 경우에 괄호 한 쌍을 맞이하게 됐을 때는 막대기의 마지막 남은 부분 때문에 sum에 1을 더했다.

그치만 사실 한가지를 간과하여 계속해서 오답이 나왔었다. 

왜일까 한참을 고민했다. 디버깅을 통해 겨우 오답이 나온 이유를 찾아내었다.

처음의 경우, (((()()) 부분에서 두 번의 연속되는 레이저를 잡아내어 sum에는 6이 들어가있었다. 

그치만 레이저가 막대기의 사이에 있었다는 정보는 스택에서 이미 제거가 된 상태였으므로 (((()()) 이 파란색 부분이 쇠막대기 임을 알 수가 없었다.

그래서 sum에 +1이 아닌 현재 스택에 남아있는 (((()()) 빨간 색 막대기 2개가 더해졌기 때문에 이상이 생긴 것이었다.

그러면 쇠막대기의 경우 인접하지 않는 괄호이며 레이저의 경우 인접한 괄호인데 이 경우를 어떻게 표시할 수 있을까..

답은 숫자였다. 

즉, '('이 나오면 '('을 스택에 넣는 것이 아닌 순서대로 숫자를 1부터 증가시키며 넣어주면 된다.

이렇게 된다면 레이저의 경우에는 '('과 ')'의 숫자가 1 차이가 나게 될 것이며 막대기는 1보다 큰 차이가 나게 된다.

(	(	(	(	)	(	)	)
1	2	3	4	5	6	7	8

레이저는 빨간 부분이며 레이저 괄호 쌍을 보면 (4, 5) , (6, 7) 여는 괄호와 닫는 괄호가 서로 1씩 차이가 난다.

파란색 막대기 부분을 보면 (3, 8) 쌍이지만 숫자차이가 1보다 큰 수임을 통해 막대기임을 알 수 있다.

코드는 다음과 같이 작성했다.

#include <iostream>
#include <string>
#include <stack>
 
using namespace std;
 
 
int main() {
    ios_base::sync_with_stdio(false);
    stack<int> s;
    int sum = 0;
    string input;
 
    cin >> input;
 
    for (int i = 0; i < input.length(); i++) {
        if (input[i] == '(')
            s.push(i);
        else { // If input is ')' 
            // First, pop the stack.
            // Second, we have to check the top whether top is '(' or not.
            // and if top is '(' that means this () is laser.            
            if (s.top() == i - 1) // this is laser.
            {
                s.pop();
                sum += s.size();
            }
            else { //not laser. just add 1 for the last one.
                s.pop();
                sum += 1;
            }
        }
    }
 
    cout << sum << endl;
    return 0;
}