정리충의 정리노트

[백준] 3425: 고스택 본문

카테고리 없음

[백준] 3425: 고스택

ioqoo 2020. 2. 3. 21:12

0. 문제 주소

 

https://www.acmicpc.net/problem/3425

 

3425번: 고스택

문제 고창영은 스택을 조금 변형해서 고스택을 만들었다. 고스택은 숫자만을 저장할 수 있고, 다음과 같은 10가지 연산을 수행할 수 있다. 편의상 스택의 가장 위에 저장된 수를 첫 번째 수라고 하고, 그 다음은 차례대로 두 번째 수, 세 번째 수라고 한다. NUM X: X를 스택의 가장 위에 저장한다. (0 ≤ X ≤ 109) POP: 스택 가장 위의 숫자를 제거한다. INV: 첫 번째 수의 부호를 바꾼다. (42 -> -42) DUP: 첫 번째 숫자를 하

www.acmicpc.net

 

 

1. 풀이

 

진짜 극혐

 

 

DIV와 MOD 연산에서 부호 처리에 관해 주저리주저리 써놓았는데, c++에서 / 과 % 연산자가 알아서 잘 해준다. (처음 알았다)

 

그거 빼곤 꾹 참고 구현만 하면 되는 문제

 

 

2. 풀이 코드

 

* 유의할 점

1. 스택에서 pop하는 명령어에 대해, empty 상태에서 꺼낼 때의 처리

2. DIV, MOD 유의

 

#include <bits/stdc++.h>
#define ll long long
#define MAX 1000000000

using namespace std;

vector<string> coms;

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    while(true){
        string com;
        cin >> com;
        if (com == "QUIT") break;
        string num;
        if (com == "NUM"){
            cin >> num;
            com = com + " " + num;
        }
        if (com == "END"){
            int n;
            cin >> n;
            for (int x=0;x<n;x++){
                stack<ll> st;
                ll v;
                cin >> v;
                st.push(v);
                bool error = false;

                for (string s: coms){
                    string curr_com = s.substr(0, 3);

                    if (curr_com == "NUM"){
                        st.push(stoll(s.substr(4)));
                    }
                    else if (curr_com == "POP"){
                        if (st.empty()){
                            cout << "ERROR\n";
                            error = true;
                            break;
                        }
                        st.pop();
                    }
                    else if (curr_com == "INV"){
                        if (st.empty()){
                            cout << "ERROR\n";
                            error = true;
                            break;
                        }
                        ll top = st.top();
                        st.pop();
                        st.push(top * (-1LL));
                    }
                    else if (curr_com == "DUP"){
                        if (st.empty()){
                            cout << "ERROR\n";
                            error = true;
                            break;
                        }
                        ll top = st.top();
                        st.push(top);
                    }
                    else if (curr_com == "SWP"){
                        if (st.empty()){
                            cout << "ERROR\n";
                            error = true;
                            break;
                        }
                        ll top1 = st.top();
                        st.pop();
                        if (st.empty()){
                            cout << "ERROR\n";
                            error = true;
                            break;
                        }
                        ll top2 = st.top();
                        st.pop();
                        st.push(top1);
                        st.push(top2);
                    }
                    else if (curr_com == "ADD"){
                        if (st.empty()){
                            cout << "ERROR\n";
                            error = true;
                            break;
                        }
                        ll top1 = st.top();
                        st.pop();
                        if (st.empty()){
                            cout << "ERROR\n";
                            error = true;
                            break;
                        }
                        ll top2 = st.top();
                        st.pop();
                        ll result = top1 + top2;
                        if (abs(result) > MAX){
                            error = true;
                            cout << "ERROR\n";
                            break;
                        }
                        st.push(result);
                    }
                    else if (curr_com == "SUB"){
                        if (st.empty()){
                            cout << "ERROR\n";
                            error = true;
                            break;
                        }
                        ll top1 = st.top();
                        st.pop();
                        if (st.empty()){
                            cout << "ERROR\n";
                            error = true;
                            break;
                        }
                        ll top2 = st.top();
                        st.pop();
                        ll result = top2 - top1;
                        if (abs(result) > MAX){
                            error = true;
                            cout << "ERROR\n";
                            break;
                        }
                        st.push(result);
                    }
                    else if (curr_com == "MUL"){
                        if (st.empty()){
                            cout << "ERROR\n";
                            error = true;
                            break;
                        }
                        ll top1 = st.top();
                        st.pop();
                        if (st.empty()){
                            cout << "ERROR\n";
                            error = true;
                            break;
                        }
                        ll top2 = st.top();
                        st.pop();
                        ll result = top2 * top1;
                        if (abs(result) > MAX){
                            error = true;
                            cout << "ERROR\n";
                            break;
                        }
                        st.push(result);
                    }
                    else if (curr_com == "DIV"){
                        if (st.empty()){
                            cout << "ERROR\n";
                            error = true;
                            break;
                        }
                        ll top1 = st.top();
                        st.pop();
                        if (st.empty()){
                            cout << "ERROR\n";
                            error = true;
                            break;
                        }
                        ll top2 = st.top();
                        st.pop();
                        if (top1 == 0LL) {
                            error = true;
                            cout << "ERROR\n";
                            break;
                        }
                        ll result = top2 / top1;
                        if (abs(result) > MAX){
                            error = true;
                            cout << "ERROR\n";
                            break;
                        }
                        st.push(result);
                    }
                    else if (curr_com == "MOD"){
                        if (st.empty()){
                            cout << "ERROR\n";
                            error = true;
                            break;
                        }
                        ll top1 = st.top();
                        st.pop();
                        if (st.empty()){
                            cout << "ERROR\n";
                            error = true;
                            break;
                        }
                        ll top2 = st.top();
                        st.pop();
                        if (top1 == 0LL) {
                            error = true;
                            cout << "ERROR\n";
                            break;
                        }
                        ll result = top2 % top1;
                        if (abs(result) > MAX){
                            error = true;
                            cout << "ERROR\n";
                            break;
                        }
                        st.push(result);
                    }
                }
                if (error) continue;
                if (st.size() != 1){
                    cout << "ERROR\n";
                    continue;
                }
                else{
                    ll ans = st.top();
                    cout << ans << "\n";
                }
            }
            cout << "\n";
            coms.clear();
        }

        coms.push_back(com);
    }

    return 0;

}

 

 

 

저작자표시
Comments