스택의 활용

01 Dec 2023 in Posts on Algo, CPP

“0x08강 - 스택의 활용”

• 덱(deque)
  • BOJ 10799 (쇠막대기)

덱(deque)

[바킹독 실전 알고리즘] 0x08강 - 스택의 활용

워크북 : 백준 10799, 2504

BOJ 10799 (쇠막대기)

내코도

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <list>
#include <utility>
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;

string  s;
stack<char> sc;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> s;
    int sum = 0;
    int depth = 0;

    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == '(')
        {
            sc.push(s[i]);
            depth++;
            
        }
        else if (s[i] == ')')
        {
            depth--;
            if (sc.top() == '(') {
                sum += depth;
            }
            else
                sum++;
            sc.push(s[i]);       
        }
    }
    cout << sum;
    return 0;
}

• 막 이것저것 넣었다 뺐다 하다보니 풀려버렸다. 이게 왜 틀렸지를 고민하는 시간보다 이게 왜 맞지를 고민하는 시간이 더 길었다.

    else if (s[i] == ')')
    {
        depth--;
        if (sc.top() == '(') {
            sum += depth;
        }
        else
            sum++;
        sc.push(s[i]);       
    }

• 이 분기에 대해 생각을 길게 했다. “)” 가 들어왔을때, 앞이 “(“ 면 레이저가 끝난거고, “)”면 막대가 끝난건데, 레이저가 끝날 때야 막대 수만큼 더해주는데, 막대가 끝날 때의 처리를 논리적으로 이해하지 못했다.

else
    sum++;

• 왜 sum에 1을 더하면 정답이 되는거지? <- 결국 스스로 알아내지 못했다. 막대가 끝났으니까 하나 더한다는걸 생각해내는게 이리 어려운가… 오늘도 슬픔stack.push();다 으아악