BOJ::3425 고스택

시사점

이해(20)

설계(x)

시간 복잡도

공간 복잡도

구현(x)

// 실수 1 : solve 에서 실패한 경우 ret = -1로 사용했었음.(음수 -1이 stack[top]인 경우 겹친다.
// 치명적 실수 2 : C = A*B 일때 (셋 다  int), A*B가 overflow가 나고도 남아서 다시 범위 안에 들어오는 경우 min max 처리 불가.
#include<iostream>
using namespace std;
#define needSize0 0
#define needSize1 1
#define needSize2 4
#define top (stk_sz-1)
#define increaseSize stk_sz++
#define decreaseSize stk_sz--
const long long _MAX_INT =1230000000;
const long long mx  =     1000000000;
const long long mn  = mx * -1;

const char END[]="END";
const char QUIT[]="QUIT";
const int MAX_CMD = 10;
const char cmds[10][4]={"NUM","POP","INV","DUP","SWP","ADD","SUB","MUL","DIV","MOD"};
enum cmdsDefine{ NUM = 0, POP, INV, DUP, SWP, ADD, SUB, MUL, DIV, MOD };

int stk_sz;
long long stack[1010];

int prg_sz;
int prg[100010][2];


// 각 명령어마다 필요한 사이즈가 있고, 그 사이즈의 체크 결과를 반환합니다.
bool ableSize(int cmd, int sz){
    if(cmd >= needSize1 && cmd < needSize2 && sz < 1) return false;
    if(cmd >= needSize2 && sz < 2) return false;
    return true;
}
// 사이즈2짜리 연산 결과가 합당한지 여부를 반환합니다.
bool isResultOkSize2(){
    bool ret = true;
    stack[top] = 0;
    decreaseSize;
    if(stack[top] < mn || stack[top] > mx) ret = false;
    return ret;
}
// a = first, b = second
// first will be poped;
void _swap(long long&a, long long&b){long long c = a; a = b; b = c;}
void _add(long long& a, long long& b){b+=a;}
void _sub(long long& a, long long& b){b-=a;}
void _mul(long long& a, long long& b){b*=a;}
void _div(long long& a, long long& b){b/=a;}
void _mod(long long& a, long long& b){b%=a;}
void _abs(long long& a){(a = (a<0?-a:a));}
// 사이즈2짜리 연산의 결과가 합당한지 여부를 반환합니다.
bool implementSize2(int cmd){
    bool ret = true;
    bool minus = false;
    switch (cmd) {
        case SWP:
            _swap(stack[top], stack[top-1]);
            break;
        case ADD:
            _add(stack[top], stack[top-1]);
            ret = isResultOkSize2();
            break;
        case SUB:
            _sub(stack[top], stack[top-1]);
            ret = isResultOkSize2();
            break;
        case MUL:
            _mul(stack[top], stack[top-1]);
            ret = isResultOkSize2();
            break;
        case DIV:
            if(stack[top] == 0){ ret = false; break; }
            if((stack[top] < 0 && stack[top-1] >0) || (stack[top] > 0 && stack[top-1] <0)) minus = true;
            _abs(stack[top]);
            _abs(stack[top-1]);
            _div(stack[top], stack[top-1]);
            if(minus) stack[top-1] *= -1;
            ret = isResultOkSize2();
            break;
        case MOD:
            if(stack[top] == 0){ ret = false; break; }
            if(stack[top-1] <0) minus = true;
            _abs(stack[top]);
            _abs(stack[top-1]);
            _mod(stack[top], stack[top-1]);
            if(minus) stack[top-1] *= -1;
            ret = isResultOkSize2();
            break;
        default:
            while(1);
            break;
    }
    return ret;
}
// 사이즈1짜리 연산을 진행합니다.
void implementSize1(int cmd){
    if(cmd == POP){
        stack[top] = 0;
        decreaseSize;
    }else if(cmd == INV){
        stack[top] *= -1;
    }else if(cmd == DUP){
        stack[top+1] = stack[top];
        increaseSize;
    }
}

int solve(int firstValue){
    int ret = 0;
    // 초기화
    for(int i = 0; i < stk_sz; i++) stack[i] = 0;
    stk_sz = 1;
    stack[top] = firstValue;
    
    // 프로그램내의 명령어 순차적 수행
    for(int i = 0; i < prg_sz; i++){
        if(stack[top] < mn || stack[top] > mx){ret = _MAX_INT; break;}
        //if(stk_sz == 0){ret = _MAX_INT; break;}
        int cmd = prg[i][0], num = prg[i][1];
        if(ableSize(cmd, stk_sz) == false){ret = _MAX_INT; break;}
        
        // SWP, AND, SUB, MUL, DIV, MOD
        if(cmd >= needSize2){
            bool isValid = implementSize2(cmd);
            // 0으로 나누거나, 0으로 나눈 나머지를 취하려 하는 경우
            // 연산의 결과가 절대값으로 10^9 범위를 넘어갈 때 false값을 갖습니다.
            if(isValid == false){ret = _MAX_INT; break;}
            
        // POP INV DUP
        }else if(cmd >= needSize1){
            implementSize1(cmd);
            
        // NUM X
        }else{
            stack[stk_sz] = num;
            increaseSize;
        }
        //if(stack[top] < mn || stack[top] > mx){ret = _MAX_INT; break;}
        //if(stk_sz == 0){ret = _MAX_INT; break;}
    }
    if(stk_sz != 1) ret = _MAX_INT;
    if(ret != _MAX_INT) ret = stack[top];
    return ret;
}
int my_strcmp(const char A[], const char B[]){
    int i = -1;
    while(A[++i]){
        if(A[i] != B[i])break;
    }
    return A[i]-B[i];
}
// 입력된 명령어의 넘버링을 반환합니다.
int getCmd(char A[]){
    for(int i = 0; i < MAX_CMD; i++){
        if(my_strcmp(cmds[i], A) == 0)return i;
    }
    return -1;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("execute.in", "r", stdin);
    //freopen("input.txt", "r", stdin);
    //freopen("execute_out.txt", "w", stdout);
    
    int first = 0;
    while(true){
        first++;
        // program
        bool isEnd = false, isQuit = false;
        char program[20]={0};
        int num = 0;
        // set program size, program
        while (true) {
            cin >> program;
            if(my_strcmp(program, END) == 0){isEnd = true; break;}
            if(my_strcmp(program, QUIT) == 0){isQuit = true; break;}
            int cmd = getCmd(program);
            if(cmd == 0) cin >> num;
            else num = 0;
            prg[prg_sz][0] = cmd; prg[prg_sz++][1] = num;
        }
        if(isQuit) break;
        if(first != 1) cout << endl;
        // input
        int cnt, first;
        cin >> cnt;
        for(int i = 0; i < cnt; i++){
            cin >> first;
            int ret = solve(first);
            if(ret == _MAX_INT) cout << "ERROR" << endl;
            else cout << ret << endl;
        }
        //cout << endl;
        prg_sz = 0;
    }
    
    return 0;
}
2nd try(01:06)
  • 4달전에 푼것과 비교해보면, 코드가 이제 읽을수 있는 정도는 된 것 같습니다.
// 신기(12) : tmp 를 switch문 안에서 선언 하면 컴파일 에러
// 실수(23) : 10^9 보다 큰지 체크는 했지만, -10^9보다 작은지는 체크 안함
#include<bits/stdc++.h>
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define PRINT_ERROR_AND_RETURN {cout<<"ERROR"<<endl; return;}
using namespace std;
typedef long long ll;
const ll LIMIT = 1000 * 1000 * 1000;
const string seq[]={"NUM", "POP", "INV", "DUP", "SWP", "ADD", "SUB", "MUL", "DIV", "MOD"};
enum seqs{NUM = 0, POP, INV, DUP, SWP, ADD, SUB, MUL, DIV, MOD};
int sz;
ll stk[1000 + 1];
vector<pair<int, ll> > cmds;
void simulate(int st){
    sz = 0;
    stk[sz++] = st;
    rep(i, 0, cmds.size()){
        int cmd = cmds[i].first;
        if(cmd < 4){
            if(sz == 0 && cmd > 0) PRINT_ERROR_AND_RETURN
            switch (cmd) {
                case NUM :
                    stk[sz++] = (int) cmds[i].second;
                    break;
                case POP :
                    sz--;
                    break;
                case INV :
                    stk[sz-1] = -stk[sz-1];
                    break;
                case DUP :
                    stk[sz] = stk[sz-1];
                    sz++;
                    break;
                default: while(1);
            }
        }else{
            ll tmp = 0;
            if(sz < 2) PRINT_ERROR_AND_RETURN
            switch (cmd) {
                case SWP:
                    swap(stk[sz-2], stk[sz-1]);
                    break;
                case ADD:
                    tmp = 1LL * stk[sz-2] + 1LL * stk[sz-1];
                    if(tmp > LIMIT || tmp < -1 * LIMIT) PRINT_ERROR_AND_RETURN
                    stk[sz-2] = (int) tmp;
                    sz--;
                    break;
                case SUB:
                    tmp = 1LL * stk[sz-2] - 1LL * stk[sz-1];
                    if(tmp > LIMIT || tmp < -1 * LIMIT) PRINT_ERROR_AND_RETURN
                    stk[sz-2] = (int)tmp;
                    sz--;
                    break;
                case MUL: // 신기 : tmp 를 switch문 안에서 선언 하면 컴파일 에러
                    tmp = 1LL * stk[sz-2] * stk[sz-1];
                    if(tmp > LIMIT || tmp < -1 * LIMIT) PRINT_ERROR_AND_RETURN
                    stk[sz-2] = (int) tmp;
                    sz--;
                    break;
                case DIV:
                    if(stk[sz-1] == 0) PRINT_ERROR_AND_RETURN
                    stk[sz-2] /= stk[sz-1];
                    sz--;
                    break;
                case MOD:
                    if(stk[sz-1] == 0) PRINT_ERROR_AND_RETURN
                    stk[sz-2] %= stk[sz-1];
                    sz--;
                    break;
                default: while(1);
            }
        }
    }
    if(sz == 1) cout << stk[0] << endl;
    else PRINT_ERROR_AND_RETURN
}
void process(){
    int cnt = 0;
    string str; int x;
    while(true){
        cnt++;
        cin >> str;
        if(strcmp(str.c_str(), "QUIT") == 0) break;
        if(cnt != 1)cout << endl;
        while(strcmp(str.c_str(), "END") != 0){
            if(strcmp(str.c_str(), "NUM") == 0){
                cin >> x;
                cmds.pb({0, x});
            }else{
                rep(i, 1, 10) if(strcmp(str.c_str(), seq[i].c_str()) == 0){
                    cmds.pb({i, 0});
                    break;
                }
            }
            cin >> str;
        }
        int cnts; cin >> cnts;
        rep(i, 0, cnts){
            cin >> x;
            simulate(x);
        }
        // init
        cmds.clear();
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    process();
    return 0;
}

디버깅(100+a)

문제에 나온 정수형의 범위와 해당 정수형을 문제에 주어진 어떤 연산을 했을때 결과값의 범위를 체크하는 것은 가장 중요한 일이라고 할 수 있겠습니다.

2nd try

  • (12m) : switch-case문 내에서는 변수를 선언할 수 없다는 사실을 처음 알았습니다.
  • (23m) : 연산 결과가 10^9 보다 큰지 체크는 했지만, -10^9보다 작은지는 체크 하지 않았습니다.