-
스택_백준_쇠막대기_10799Algorithm 2018. 8. 14. 14:26
여는 괄호가 나왔을때 이는 레이저 혹은 쇠막대기 둘 중에 하나다.
따라서 여는 괄호 직후 바로 닫는 괄호가 나오면 레이저이고 그 외에는 모두 쇠막대기를 뜻한다.
시간복잡도는 O(N) * O(1)로 O(N)이다.
123456789101112131415161718192021222324252627282930#include <iostream>#include <string>#include <stack>using namespace std;int main() {int result = 0;string input;stack <char> s;cin >> input;for (int i = 0; i < input.size(); i++) {if (input[i] == '(') {s.push('(');}else {if (input[i - 1] == '(') {s.pop(); // before ( pushresult += s.size(); //The size of the stack is the number of bars.}//Laserelse {s.pop();result++;}//Bar}}cout << result << endl;return 0;}cs 'Algorithm' 카테고리의 다른 글
스택_백준_스택 수열_1874 (0) 2018.08.14 스택_백준_에디터_1406 (0) 2018.08.14 스택_백준_괄호_9012 (0) 2018.08.14 스택_이론 (0) 2018.08.14 알고리즘과 입출력_백준_2444 (0) 2018.08.14