알고리즘 :: 백준 :: 스택 :: 10799 :: 쇠막대기

문제

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

문제접근

개인적으로 한참동안 고민했던 어려운 문제였다. 명확한 풀이법이 생각나지 않았다.

• 스택을 사용한다.
• ) 닫는 괄호문자를 만나면 이 문자가 레이저를 의미하는지, 쇠막대기의 끝을 의미하는지 파악하는것이 핵심이다.

  • )문자의 인덱스와 스택의 top에 있는 인덱스 차이가 1이라면 레이저를 의미한다.

  • )문자의 인덱스와 스택의 top에 있는 인덱스 차이가 1 이상이라면 쇠막대기를 의미한다.

    

• 레이저가 관통하는 막대의 수 + 1이 분할되는 막대의 수이므로 레이저가 발견될 때는 현재 스택에 있는 막대의 개수를 답에 더해주고, 쇠막대기의 끝이 발견될 때는 답에 1을 더해준다.

코드

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

string input;

int solve() {
    stack<int> stk;
    int ret = 0;
    for (int i = 0; i < input.length(); ++i) {
        if (input[i] == '(') stk.push(i);
        else {
            int diff = i - stk.top();
            stk.pop();
            ret = (diff == 1) ? (ret + stk.size()) : (ret + 1);
        }
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> input;
    cout << solve() << '\n';
}

결과