백준 10799(쇠막대기) c++

문제

10799번: 쇠막대기

위와 같은 괄호가 주어졌을 때, 괄호가 바로 ()이면 레이져이고, '('는 쇠막대기의 시작점, ')'는 쇠막대기의 끝점입니다.

레이져를 쏘았을 때 쇠막대기의 조각을 세는 문제입니다. 위의 그림에서는 17개 입니다.

 

처음에는 레이저의 좌표와 쇠막대기의 좌표를 기록해 하나하나 비교해가면서 레이져가 쇠막대기를 겹치는 부분을 세었습니다.

물론 정답은 맞았지만, 시간이 매우 오래 걸렸습니다. (O(n^2))

 

새로운 방법은 '(' 가 나오면 무조건 스택에 넣어줍니다. 그러다가 레이져가 나오면 현재 스택에 쌓아놓은 크기를 누적해서 더해줍니다.

물론 ')' 가 나오면 무조건 pop을 해줘야 합니다. 

그리고 레이저의 ')'가 아니라 막대기의 ')'가 나오면 +1을 누적해서 더해줍니다.

그러면 O(n)으로 문제를 해결했습니다.

---

전체코드입니다.

#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#define INF 2000000000
using namespace std;
using ll = long long;
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    string s;
    cin >> s;
    stack<char> st;
    int result = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '(')
            st.push(s[i]);
        else if (s[i] == ')')
        {
            if (s[i - 1] == '(')
            {
                st.pop();
                result += st.size();
            }
            else
            {
                result++;
                st.pop();
            }
        }
    }
    cout << result;
    return 0;
}