백준 10799번 쇠막대기 - C++ 풀이

---

 

1. 여는 괄호를 만나면 막대를 쌓는다.
2. 레이저의 닫는 괄호를 만나면 쌓인 막대 개수만큼 조각이 생성된다.
3. 막대의 닫는 괄호를 만나면 조각이 1개 생성된다.

 

1. 여는 괄호를 만나면 막대를 쌓는다.

 여는 괄호를 만나면 막대의 시작점이므로 막대를 쌓아준다. 쌓인 막대의 개수를 저장해둘 것이다. 이때 여는 괄호가 막대의 시작이 아니라 레이저일 수도 있는데, 막대 개수를 -1부터 카운트하면 따로 예외 처리하지 않아도 된다.

 

2. 레이저의 닫는 괄호를 만나면 쌓인 막대 개수만큼 조각이 생성된다.

 레이저의 닫는 괄호를 만나면, 쌓인 막대 개수만큼 조각이 생성된다. 직전 괄호가 여는 괄호라면 레이저인 것으로 판단할 수 있다.

 

3. 막대의 닫는 괄호를 만나면 조각이 1개 생성된다.

 레이저의 닫는 괄호가 아니라 막대의 닫는 괄호라면, 해당 막대만 끝이 나므로 조각이 1개 생성된다.

 

반응형

---

#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    string s; cin >> s;
    
    long long stackTop = -1, sum = 0;
    for (int i=0; i<s.size(); i++) {
        if (s[i] == '(') stackTop++;
        else {
            if (s[i-1] == '(') sum += stackTop; // 레이저인 경우 쌓인 막대 개수만큼 조각이 추가됨
            else sum += 1;                      
            stackTop--;
        }
    }
    
    cout << sum;

    return 0;
}