쇠막대기 (feat. 백준, 10799번)

쇠막대기
https://www.acmicpc.net/problem/10799

10799번: 쇠막대기

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    string str;
    cin >> str;
    stack<pair<int, int>> arr1;
    vector<int> arr2;
    vector<pair<int, int>> arr3;
    for(register int i = 0; i < str.size(); ++i){
        if(str.at(i) == '('){
            if(str.at(i + 1) == ')')
                arr2.push_back(i + 1);
            else
                arr1.push(make_pair(i, 0));
        }
        else if(str.at(i) == ')' && str.at(i - 1) == ')'){
            auto p = arr1.top(); arr1.pop();
            p.second = i;
            arr3.push_back(p);
        }
    }
    register int ans = 0;
    for(auto& stick : arr3){
        register int idx = 0;
        for(auto& laser : arr2)
            if(stick.first < laser && laser < stick.second)
                ++idx;
        if(idx != 0)
            ans += idx + 1;
    }
    cout << ans;
    return 0;
}
// *&)*@*

 

반응형

1. 가장 최근에 삽입된 쇠막대기의 시작점을 알아오기 위해 자료구조 stack을 사용했습니다.
2. 쇠막대기가 끝나는 위치에서 가장 최근의 쇠막대기의 끝점을 삽입하고 보관하였습니다.
3. 레이저의 위치를 기준으로 보관된 모든 쇠막대기가 레이저의 인덱스에 포함되는지를 확인하고 이를 카운팅했습니다.