[백준] 10799번: 쇠막대기

Kim Yuhyeon·2022년 3월 28일

cpp 백준 알고리즘

알고리즘 + 자료구조

목록 보기

28/161

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

문제

알고리즘 접근 방법

cnt : 잘려진 쇠막대기 조각의 총 개수
stack : 현재 있는 쇠막대기의 개수
text : 입력받은 문자열
왼쪽부터 한 글자씩 for문을 이용하여 체크한다.

쇠막대

쇠막대가 열릴 경우

( 모양일 때는 쇠막대가 열릴 경우일 수도 있고, 레이져일 수도 있다.
이는 후에 검사한다.
text[i] == '('

일단 이 경우에는 stack 에 push(text[i])하여 쇠막대의 개수를 하나 늘려준다.

쇠막대가 닫힐 경우

쇠막대가 닫힐 경우는 )) 이 모양 일 때이다.
text[i-1] == ')' && text[i] == ')'

stack 에서 pop()하여 쇠막대의 개수를 하나 줄여주고, cnt++ 해준다.

레이저

레이져가 나오는 경우는 () 이 모양
text[i-1] == '(' && text[i] == ')'

아까 쇠막대에 일단 +1 했던 걸
stack 에서 pop()하여 쇠막대의 개수를 하나 줄여주고

cnt에 현재 있는 쇠막대 개수(stack.size())만큼 더해준다.

풀이

#include <iostream>
#include <string>
#include <stack>

using namespace std;

stack<char> a;

int main(){

    string text;
    cin >> text;

    int cnt = 0;

    for (int i=0; i<text.length(); i++){
        if(text[i] == '('){ 
            a.push(text[i]);
        }
        else if (text[i-1] == '(' && text[i] == ')'){ // 레이져
            a.pop();
            cnt += a.size();
        }
        else if (text[i-1] == ')' && text[i] == ')'){ // 쇠막대 끝
            a.pop();
            cnt ++;
        }

    }

    cout << cnt << '\n';
    
    return 0;
}