[백준] 3425. 고스택

문제

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

풀이

정말 어마어마어마어마한 시도 끝에 간신히 맞췄다. 왜 틀렸나 봤더니 초기화를 잘못해줬다... 자신의 코드가 너무 완벽해서 당최 어디서 틀렸는지 알 수 없다면 초기화 부분을 꼭 확인해보자. 그리고 아래를 잘 구현했는지, 혹시 어떤 조건에서 아래 조건들이 제대로 필터링 안되는지 확인해보자. 본인은 return 하는 과정에서 스택이 초기화가 제대로 안되서 수십번의 실패를 거듭했었다.

1. 숫자가 부족해서 연산을 수행할 수 없을 때, 0으로 나눴을 때 (DIV, MOD), 연산 결과의 절댓값이 109를 넘어갈 때는 모두 프로그램 에러이다.

2. 음수 나눗셈에 대한 모호함을 피하기 위해 다음과 같이 계산한다. 나눗셈의 피연산자에 음수가 있을 때는, 그 수를 절댓값을 씌운 뒤 계산한다. 그리고 나서 몫과 나머지의 부호는 다음과 같이 결정한다. 피연산자중 음수가 한 개일때는 몫의 부호가 음수이다. 이 경우를 제외하면 몫의 부호는 항상 양수이다. 나머지의 부호는 피제수의 부호와 같다.

3. 프로그램 에러가 발생했을 경우에는, 현재 프로그램의 수행을 멈추고, 그 다음 어떤 명령도 수행하지 않는다.

혹시 런타임 에러가 발생하면 스택이나 명령어 입력을 받는 자료구조 등을 제대로 추가 및 삭제하는지 확인하자. 보통 그쪽에서 실수가 나올 것 같다. 위 과정을 제대로 구현했는데 실패한다면, 분명 어떤 조건에서 저 부분이 제대로 걸러지지 않거나, 자료구조를 초기화하지 않았거나, 조건을 잘못 구현했거나 그 정도 이유일텐데, 도저히 찾을 수 없으면 필자처럼 무수한 시도를 하지 말고 질문 게시판에 올려보는 것도 나쁘지 않을 것 같다. 아님 누추하지만 이 블로그에 있는 지저분한 코드를 가져다 써도 된다. 아마 이 글을 읽고 있는 여러분의 코드와 별 차이가 없을테니 딱히 분석이 필요할 것 같지는 않다.

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>

using namespace std;
long long MAX = 1000000000;

stack<long long> s;

bool NUM(long long x){
    s.push(x);
    return true;
}

bool POP(){
    if(s.empty()){
        cout << "ERROR" << '\n'; return false;
    }
    s.pop();
    return true;
}

bool INV(){
    if(s.empty()){
        cout << "ERROR" << '\n'; return false;
    }
    long long t = s.top(); 
    s.pop();  s.push(-t);
    return true;
}

bool DUP(){
    if(s.empty()){
        cout << "ERROR" << '\n'; return false;
    }
    long long t = s.top(); s.push(t);
    return true;
}

bool SWP(){
    if(s.size() < 2){
        cout << "ERROR" << '\n'; return false;
    }
    long long a = s.top(); s.pop();
    long long b = s.top(); s.pop();
    s.push(a); s.push(b);
    return true;
}

bool ADD(){
    if(s.size() < 2){
        cout << "ERROR" << '\n'; return false;
    }
    long long a = s.top(); s.pop();
    long long b = s.top(); s.pop();
    if(abs(a + b) > MAX){
        cout << "ERROR" << '\n'; return false;
    }
    s.push(a + b);
    return true;
}

bool SUB(){
    if(s.size() < 2){
        cout << "ERROR" << '\n'; return false;
    }
    long long a = s.top(); s.pop();
    long long b = s.top(); s.pop();
    if(abs(b - a) > MAX){
        cout << "ERROR" << '\n'; return false;
    }
    s.push(b - a);
    return true;
}

bool MUL(){
    if(s.size() < 2){
        cout << "ERROR" << '\n'; return false;
    }
    long long a = s.top(); s.pop();
    long long b = s.top(); s.pop();
    if(abs(b * a) > MAX){
        cout << "ERROR" << '\n'; return false;
    }
    s.push(a * b);
    return true;
}

bool DIV(){
    if(s.size() < 2){
        cout << "ERROR" << '\n'; return false;
    }
    long long a = s.top(); s.pop();
    long long b = s.top(); s.pop();
    if(a == 0){
        cout << "ERROR" << '\n'; return false;
    }
    if((a > 0 && b >= 0)){
        s.push(abs(b / a));
    }
    else if((a < 0 && b < 0)){
        s.push(abs(b / a));
    }
    else{
        s.push(-abs(b / a));
    }
    return true;
}

bool MOD(){
    if(s.size() < 2){
        cout << "ERROR" << '\n'; return false;
    }
    long long a = s.top(); s.pop();
    long long b = s.top(); s.pop();
    if(a == 0){
        cout << "ERROR" << '\n'; return false;
    }
    if(b >= 0){
        s.push(abs(b % a));
    }
    else if(b < 0){ 
        s.push(-abs(b % a));
    }
    return true;
}



void calc(vector<pair<string, int> > order){
    for(int i = 0; i < order.size(); i++){
        if(order[i].first == "NUM"){
            if(!NUM(order[i].second)) return;
        }
        else if(order[i].first == "POP"){
            if(!POP()) return;
        }
        else if(order[i].first == "INV"){
            if(!INV()) return;
        }
        else if(order[i].first == "DUP"){
            if(!DUP()) return;
        }
        else if(order[i].first == "SWP"){
            if(!SWP()) return;
        }
        else if(order[i].first == "ADD"){
            if(!ADD()) return;
        }
        else if(order[i].first == "SUB"){
            if(!SUB()) return;
        }
        else if(order[i].first == "MUL"){
            if(!MUL()) return;
        }
        else if(order[i].first == "DIV"){
            if(!DIV()) return;
        }
        else if(order[i].first == "MOD"){
            if(!MOD()) return;
        }

        if(!s.empty() && abs(s.top()) > MAX){
        cout << "ERROR" << '\n';
        while(!s.empty()){
            s.pop();
        }
        return;
        }
    }
    if(s.size() != 1) {
        cout << "ERROR" << '\n';
        while(!s.empty()){
            s.pop();
        }
        return;
    }
    
    cout << s.top() << '\n';
    s.pop();
}


int main(){

    ios::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);

    vector<pair<string, int> > order;

    while(true){
        while(true){ 
            string s; cin >> s;
            if(s == "QUIT") return 0; 
            if(s == "END"){
                break;
            }
            else if(s == "NUM"){
                long long t; cin >> t;
                order.push_back(make_pair(s, t));
            }
            else order.push_back(make_pair(s, 0));
        }
        int N; cin >> N;
        for(int i = 0; i < N; i++){
            long long t; cin >> t; 
            s.push(t);
            calc(order);
            // 위에서 return 되는 조건에서 스택을 비우질 못한듯
            while(!s.empty()){
                s.pop();
            }
        }
        cout << '\n';
        order.clear();
        
    }

   
    return 0;
}

Cat On The Keyboard

이 블로그 검색

[백준] 3425. 고스택

문제

풀이

댓글

댓글 쓰기