백준 10799 쇠막대기 c++ [컴공과고씨]

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

10799번: 쇠막대기

첫 번째로 ) 나왔을 때 구별 해주어야할 것은 막대기의 끝인지 아니면 레이저인지 구별하는 것이다.

) 나오기 바로 직전이 ( 였다면 레이저이고 )이면 막대기의 끝이다.

이것을 이용하여 ( 나올때 카운트를 해준다. 그리고 ) 나왔을 때 (하나는 사라지는 것이므로 카운트 개수를 -1해준다.

) 나왔을 때 레이저라면 앞에 ( 개수를 세준수 만큼 잘린 막대기 개수가 나오므로 총 막대기 개수에 저장해준다. 만약 막대기 끝인 경우에는 총 막대기 개수에 +1을 해주면 된다.  

 

 

단계별 풀이

1. ( 이면 큐에 푸쉬 해줌. 이 때 다음 입력이 ) 경우 레이저일 수 있음(bool 변수로 표시), 막대기 개수 +1

2. ) 경우 bool 변수로 레이저인지 막대기 끝인지 구별

3. 레이저일 경우 막대기 개수 -1. 레이저 변수로 다음 입력은 레이저가 될 수 없음 표시. ans += 막대기 개수

4. 막대기 끝일 경우 막대기 개수 -1. ans += 1

 

#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main(){
    string s;
    queue<char> q;
    cin >> s;
    bool laser = false; // 레이저 인지
    int cnt = 0;
    int ans = 0;
    for (int i = 0; i < s.length();i++){
        if(s[i] == '('){ 
            q.push(s[i]);
            laser = true; // 다음 입력이 )일경우 레이저
            cnt++;
        }else if(s[i] == ')'){
            if(laser){ // 레이저 일 경우
                cnt -= 1;
                laser = false; // 연속으로 레이저는 나올 수 없음
                ans += cnt;
            }else{// 막대기 끝일 경우
                cnt -= 1;
                ans += 1;
            }
        }
    }
    cout << ans;
    return 0;
}//18min

체감 난이도	걸린시간	참고	사용 문법
하	18min	x	queue