백준 10799번 : 쇠막대기 c++

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

10799번: 쇠막대기

문제를 봤을 때 어떻게 구현해야 할지 감이 잡히지 않는 문제였다.

💡문제 조건

• 여러 개의 쇠막대기를 레이저로 절단하는데, 레이저로 인해 잘려진 쇠막대기의 수를 구하는 문제이다.
• 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
• 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.
• stack을 이용해서 쇠막대기의 수를 구해준다.

그림과 같이 제시된 test case의 문자열로는 17개의 쇠막대기가 생성된다. 

')'가 입력되었을 때, 레이저와 막대인 두 가지 경우가 있다. -> 앞이 '('라면 레이저이고 그것이 아니라면 막대의 끝임을 알 수 있다.

접근 과정

• '('가 들어오면 stack에 push한다.
• ')'가 들어왔을때, 레이저와 막대인 두 가지 경우가 있다. => 앞이 '(' 라면 레이저이고, 그것이 아니라면 막대의 끝이다.
• 레이저일 때는, () 에서 앞의 '('를 처음에 push 해줬기 때문에, 이것을 pop 해준다. 이후, 막대의 개수만큼 추가해주는데, 이때 st.size()를 이용한다.
• 막대의 끝일 때는, 막대의 개수를 1개 감소 (pop)한 후 막대 한개가 절단된 것과 같은 상황임으로 1을 추가한다.

그림으로 설명하면, 처음 레이저를 만난 상황에서 스택에 3번의 push가 일어났음을 알 수 있다.

')' 가 입력되어 '(' ')' 인 레이저가 완성되었으므로 '('를 pop 해준 후 스택의 size만큼 정답에 더해준다. 3개의 쇠막대기를 구했다.

 

그 다음 문자열도 레이저이므로, 스택의 size인 3을 정답(막대의 총 개수)에 더해준다. 현재까지 6개의 쇠막대기를 구했다.

그 다음은 앞이 '(' 가 아니므로 레이저가 아닌 쇠막대기의 끝이다.

이 경우에는 pop을 해주고, 막대 한개가 절단된 것과 같은 상황이므로 1을 추가한다. 빨간색으로 표시한 막대의 처리가 끝났음을 알 수 있다.

코드

string s;
int ans = 0;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> s;
    stack<char> st;
    for(int i=0;i<s.length();i++){
        if(s[i]=='(') st.push(s[i]);
        else{ //')'
            if(s[i-1]=='('){ //레이저인 경우
                st.pop();
                ans += st.size();
            }
            else{ //막대의 끝인 경우
                st.pop();
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}