[백준] 10799번 SIlver 2 쇠막대기, C++ 코드

 

 

스택으로 풀었지만, 스택으로 size()를 사용하면 O(n) 시간 복잡도가 사용된다.

이에 따라 그냥 int 값으로 저장하면 O(1)로 줄어드니 그게 더 효율적인 것 같다.

 

효율적인 방법은 후자지만, 막상 시험때는 잘 생각나지 않을 수도..?

 

스택 풀이법 1

#include <iostream>
#include <stack>

#define endl "\n"

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    stack<char> stack;
    int result = 0;
    
    char c;
    char before = '\0';
    while(cin.get(c)) {
        if (c == '(') {
            stack.push(c);
        } else if (c == ')') {
            stack.pop();
            result += (before == '('? stack.size() : 1);
        }

        before = c;
    }

    cout << result << endl;
}

 

 

int 변수값 풀이법 2

#include <iostream>

#define endl "\n"

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int result = 0;
    int openCnt = 0;
    
    char c;
    char before = '\0';
    while(cin.get(c)) {
        if (c == '(') {
            openCnt++;
        } else if (c == ')') {
            openCnt--;
            result += (before == '('? openCnt : 1);
        }

        before = c;
    }

    cout << result << endl;
}