문제 링크: https://www.acmicpc.net/problem/10799


스택을 활용하여 풀었습니다.


주어진 조건들에서, 여는 괄호 '('를 만나면 모두 스택에 넣었다가, ')'를 만나면 레이저인지 쇠파이프의 끝인지 구분하고, 스택에서 '('를 하나 꺼냅니다.

')'가 레이저를 의미하면, 쌓여있는 쇠파이프가 모두 잘리므로 결과에 그만큼 더해줍니다. (파이프의 수가 스택에 저장된 원소의 수와 같음을 이용합니다.)

')'가 파이프의 끝을 의미하면, 결과에 파이프 한 개를 더해줍니다.


C++

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

int laser(string);

int main() {
    string str;
    cin >> str;
    cout << laser(str) << endl;

    return 0;
}

int laser(string str) {
    stack cStack;
    int result = 0; // 잘려나온 조각 수를 저장할 변수 
    
    for(int i = 0; i < str.length(); i++) {
        if(str[i] == '(') cStack.push(str[i]);  // (는 stack에 push
        else {  // 여는 괄호가 아니라면: 레이저인지 파이프의 끝인지 구분해야 
            cStack.pop();

            if(str[i - 1] == '(') result += cStack.size();  // 레이저이면: 파이프 수(=스택의 수) 만큼 잘려나감  
            else result++; // 파이프의 끝이면: 한 조각 늘어남 
        }
    }

    return result; // 총 조각 수 반환 
}

'Algorithm > BOJ' 카테고리의 다른 글

BOJ 2493번: 탑  (0) 2018.10.03
BOJ 9935번: 문자열 폭발  (0) 2018.10.03
BOJ 9012번: 괄호  (0) 2018.10.03
BOJ 10799번: 쇠막대기  (0) 2018.10.03
BOJ 1001번: A-B  (0) 2018.10.03
BOJ 1000번: A+B  (0) 2018.10.03

+ Recent posts