ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 스택_백준_쇠막대기_10799
    Algorithm 2018. 8. 14. 14:26

    여는 괄호가 나왔을때 이는 레이저 혹은 쇠막대기 둘 중에 하나다.

    따라서 여는 괄호 직후 바로 닫는 괄호가 나오면 레이저이고 그 외에는 모두 쇠막대기를 뜻한다.

    시간복잡도는 O(N) * O(1)로 O(N)이다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    #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 ( push
                    result += s.size(); //The size of the stack is the number of bars.
                }//Laser
     
                else {
                    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
Designed by Tistory.