스택

“0x05강 - 스택”

스택

[바킹독 실전 알고리즘] 0x05강 - 스택

워크북 : 백준 1874, 2493, 6198

BOJ 1874 (스택 수열)


#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;

int tc;
stack<int>  s;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> tc;
    int cur = 1;
    vector<char> ans;

    for (int i = 0; i < tc; i++) {
        int num; cin >> num;
        for (int i = cur; i <= num; i++) {
            ans.push_back('+');
            s.push(cur);
            cur++;
        }
        if (s.top() != num) {
            cout << "NO";
            return 0 ;
        }
        else {
            ans.push_back('-');
            s.pop();        
        }
    }
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << '\n';
    } 

    return 0;
}
  • 난이도는 제일 낮은데 개인적으로 이해하기는 제일 어려웠던 문제. 절대 맨땅에서 생각해내지 못했을 것 같다.

BOJ 2493 (탑)


#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;

int N;
stack< pair<int,int> > s;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;

    for (int i = 1; i <= N; i++) {
        int num;
        cin >> num;
        while (s.size() && s.top().first <= num)
            s.pop();
        if (s.empty()) {
            cout << '0' << ' ';
        } else {
            cout << s.top().second << ' ';
        }
        s.push(make_pair(num, i));
    }

    return 0;
}
  • 첫번째로 스택에 pair로 저장하는 거랑, 두번째로
    while (s.size() && s.top().first <= num)
        s.pop();

이 라인이 킬링 포인트다. 여기서 뇌 안뚫어놨으면 밑에 문제는 절대 혼자 못 풀었을거다.

BOJ 6198 (옥상 정원 꾸미기)


#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;

int N;
stack< pair<int, int> > s;
vector<int> v;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    long long sum = 0;
  
    for (int i = 1; i <= N; i++) {
        int num;
        cin >> num;
        while (s.size() && s.top().first <= num) {
            s.pop();
        }
        s.push(make_pair(num, s.size()));
        sum += s.top().second;
    }
    cout << sum;
    return 0;
}
  • 앞에 두 문제는 보고 풀었는데 이거는 어떻게 혼자 풀었다. 3시간넘게걸림, 앞에 탑 문제에서 언급했던 스택에 페어로 저장하기 그리고
    while (s.size() && s.top().first <= num)
        s.pop();

이 라인의 아이디어를 응용해서 풀어낼 수 있었다. 아래 그림은 생각하면서 그린거.


  • 스택 쉬워보이는줄알았더니 실버상위만 되도 개어렵다; 역시 쉬운거하나없다.