stack 개념 정리

LIFO : Last In First Out

그냥 한쪽 끝 통로가 막혀있고 다른쪽은 뚫려 있는 원통형 관을 생각하자.
이게 다다.

• push
• pop
• top
• empty
• size

문제1 #boj 1874

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다

풀이

#include <iostream>
#include <stack>
#include <string>
using namespace std;

#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

int main()
{
    FASTIO;

    int n; cin >> n;
    stack<int> st;
    string ans;
    int m = 0;

    while (n--) {
        int c; cin >> c;
        if (c > m) {
            while (c > m) {
                st.push(++m);
                ans += '+';
            }
            st.pop();
            ans += '-';
        } else {
            bool found = false;
            if (!st.empty()) {
                int top = st.top();
                st.pop();
                ans+='-';
                if (c == top) {
                    found = true;
                }
            }
            if (!found) {
                cout << "NO" << '\n';
                return 0;
            }
        }
    }
    for (auto x : ans) {
        cout << x << '\n';
    }

}

문제2 #boj 17423

문제

문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다.

먼저, 문자열 S는 아래와과 같은 규칙을 지킨다.

알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('<', '>')로만 이루어져 있다.
문자열의 시작과 끝은 공백이 아니다.
'<'와 '>'가 문자열에 있는 경우 번갈아가면서 등장하며, '<'이 먼저 등장한다. 또, 두 문자의 개수는 같다.
태그는 '<'로 시작해서 '>'로 끝나는 길이가 3 이상인 부분 문자열이고, '<'와 '>' 사이에는 알파벳 소문자와 공백만 있다. 단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다. 태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다.

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 100,000 이하이다.

출력

첫째 줄에 문자열 S의 단어를 뒤집어서 출력한다.

풀이

#include <iostream>
#include <stack>
#include <string>
using namespace std;

#define FASTIO   cin.tie(0);  cout.tie(0); ios_base::sync_with_stdio(0);

void print(stack<char> &st) {
    while(!st.empty()) {
        cout << st.top();
        st.pop();
    }
}

int main() {
    FASTIO;
    string s;
    getline(cin , s);
    bool tag = false;
    stack<char> st;

    for (char ch : s) {
        if (ch == '<') {
            print(st);
            tag = true;
            cout << ch;
        } else if (ch == '>') {
            tag = false;
            cout << ch;
        } else if (tag) {
            cout << ch;
        } else {
            if (ch == ' ') {
                print(st);
                cout << ch;
            } else {
                st.push(ch);
            }
        }
    }
    print(st);
}