[백준,c++] 10799번 - 쇠막대기

문제

10799번: 쇠막대기

 

코드

#include <iostream>
#include <stack>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    string s; cin>>s;
    stack<char>st;
    int ans = 0;
    
    for(int i=0; i<s.length(); i++){
        if(s[i]=='(') st.push(s[i]);
        else if(s[i]==')'&&s[i-1]=='('){
            st.pop();
            ans += st.size();
        }
        else{
            st.pop();
            ans++;
        }
    }
    cout<<ans;
}

 

풀이

간단한 예제인 ( ( ( ) ) )라는 입력으로 한번 생각해 봅시다.

위 이미지를 에제로 코드를 설명해 보겠습니다.

• 입력이 '('일 때는 스택에 넣습니다.
• 입력이 ')'일 때는 이전 입력과 비교(스택 말고 문자에서 비교)하여 레이저인지 아닌지 체크합니다.
  • -> 만약 레이저 일 경우 스택의 사이즈만큼 더해줍니다. (스택의 사이즈는 위 이미지 1번과 2번 막대기)
  • -> 레이저가 아닐 경우 그냥 1씩 더해주면 3번과 4번을 각각 더해주는 것과 같으므로 1씩 더해줍니다.

문자열의 길이만큼만 for문을 돌려주면 때문에 시간 복잡도는 O(n)이며 구현은 어렵지 않았으나, 해결 아이디어를 떠올리는데 꽤 많은 시간이 걸린 문제였습니다.