BOJ 3425

16 May 2020 • ProblemSolving

고스택

문제출처

문제 해석

정해진 수를 연산하였을 때의 결과를 출력하는 문제입니다.

연산은 다음 10가지와 같습니다.

  1. NUM X: X를 스택의 가장 위에 저장합니다.
  2. POP : 스택 가장 위의 숫자를 제거합니다.
  3. INV : 첫번째 수의 부호를 바꿉니다.
  4. DUP : 첫번째숫자를 하나더 스택에 추가합니다.
  5. SWP : 첫번째와 두번째 숫자를 바꿉니다.
  6. ADD : 두번째 + 첫번째
  7. SUB : 두번째 - 첫번째
  8. MUL : 두번째 x 첫번째
  9. DIV : 두번째 / 첫번째
  10. MOD : 두번째 % 첫번째

프로그램이 에러가 나는 경우는 다음과 같습니다.

  1. 0으로 나누는 경우 (DIV,MOD)
  2. 숫자가 부족해서 연산을 수행할 수 없는 경우
  3. 연산 결과의 절대값이 109를 넘는 경우

DIV시 피연산자가 음수일 때, 먼저 절대값을 취해준 후, 음수의 개수가 한개일때만 최종값을 음수로 변경시킵니다.

MOD시 피연산자가 음수일 때, 두번째 숫자의 부호를 따릅니다.

설계(20)

구현은 어렵지 않지만 고려해야하는 부분이 아주 많은 까다로운 문제입니다.

먼저, 스택을 구현합니다. MUL 연산을 할 때 int형 범위를 넘어설 수 있기 때문에 long long형으로 선언합니다.

POP,INV,DUP인데 스택이 비어있으면 에러를 출력합니다.

위의 경우가 아니고, NUM이 아닐때 스택에 있는 수가 1개 이하이면 에러를 출력합니다.

ADD, SUB,MUL연산을 수행할 때 연산결과의 절대값이 109를 넘으면 에러를 출력합니다.

DIV,MOD 연산을 수행할 때, 첫번째 숫자가 0이면 에러를 출력합니다.

만약 연산을 모두 수행한 후, 스택에 남아있는 숫자가 한개가 아니면 에러를 출력합니다.

구현(60)

코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long ll;
#define MAXN 100000
#define INF 1E9

struct node {
    string s;
    int num;
};

node order[MAXN];
ll st[1001];
int s_idx;
int idx;
void Swap(ll& a, ll& b) {
    ll tmp = a;
    a = b;
    b = tmp;
}
bool is_range(ll x) {
    return abs(x) <= INF;
}
ll go(int x) {
    st[s_idx++] = x;
    for (int i = 0; i < idx; i++) {
        string s = order[i].s;
        int num = order[i].num;
        if ((s == "POP" || s == "INV" || s == "DUP") && s_idx == 0) return 1E10;
        if (s != "NUM" && !(s == "POP" || s == "INV" || s == "DUP") && s_idx <= 1) return 1E10;
        if (s == "NUM") {
            st[s_idx++] = num;
        }
        else if (s == "POP") {
            s_idx--;
        }
        else if (s == "INV") {
            st[s_idx - 1] *= -1;
        }
        else if (s == "DUP") {
            int tmp_num = st[s_idx - 1];
            st[s_idx++] = tmp_num;
        }
        else if (s == "SWP") {
            Swap(st[s_idx - 1], st[s_idx - 2]);
        }
        else if (s == "ADD") {
            ll num1 = st[--s_idx];
            ll num2 = st[--s_idx];
            if (!is_range(num1 + num2)) return 1E10;
            st[s_idx++] = num1 + num2;
        }
        else if (s == "SUB") {
            ll num1 = st[--s_idx];
            ll num2 = st[--s_idx];
            if (!is_range(num2 - num1)) return 1E10;
            st[s_idx++] = num2 - num1;
        }
        else if (s == "MUL") {
            ll num1 = st[--s_idx];
            ll num2 = st[--s_idx];
            if (!is_range(num2 * num1)) return 1E10;
            st[s_idx++] = num2 * num1;
        }
        else if (s == "DIV") {
            ll num1 = st[--s_idx];
            ll num2 = st[--s_idx];
            if (num1 == 0) return 1E10;
            if (!(num1 < 0 && num2 < 0) && (num1 < 0 || num2 < 0)) st[s_idx++] = -(abs(num2) / abs(num1));
            else st[s_idx++] = abs(num2) / abs(num1);
        }
        else if (s == "MOD") {
            ll num1 = st[--s_idx];
            ll num2 = st[--s_idx];
            if (num1 == 0) return 1E10;
            if (num2 < 0) st[s_idx++] = -(abs(num2) % abs(num1));
            else st[s_idx++] = abs(num2) % abs(num1);
        }
    }
    if (s_idx != 1) return 1E10;
    return st[0];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (1) {
        string s;
        int num;
        cin >> s;
        idx = 0;
        if (s == "QUIT") return 0;
        if (s == "NUM") {
            cin >> num;
            order[idx++] = { s,num };
        }
        else if (s != "END") order[idx++] = { s,0 };
        if (s != "END") {
            while (1) {
                cin >> s;
                if (s == "END") break;
                if (s == "NUM") {
                    cin >> num;
                    order[idx++] = { s,num };
                }
                else order[idx++] = { s,0 };
            }
        }

        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            memset(st, 0, sizeof(st));
            s_idx = 0;
            cin >> num;
            ll ans = go(num);
            if (ans == 1E10) {
                cout << "ERROR\n";
            }
            else {
                cout << ans << "\n";
            }
        }
        cout << "\n";
    }
}
디버깅

실수를 많이해서 디버깅에 거의 모든 시간을 쏟아부었습니다.

  1. 명령어가 아무것도 없고 END만 나오는 경우를 고려하지 않았습니다.

  2. 연산을 수행한 후, 에러가 날 경우 -1을 출력하는 실수를 하였습니다. -1자체의 값이 나올 수 있기 때문에 아예 나올 수 없는 1010를 리턴하도록 변경하였습니다.

  3. 절대값 범위 체크를 할 때 딱 109인 경우, 에러라고 인식하는 오류를 범했습니다.

제출결과

20 ms

마무리

너무나 까다로웠던 구현문제였습니다.

실수를 유발하는 함정들이 무더기로 있기 때문에, 코테를 준비하는 사람들은 꼭 한번씩 풀어보면 좋을 법한 문제입니다.

이를 통해서 내가 어느 부분을 보통 간과하는지 알 수 있을 것입니다.

 BOJ  CERC 2011

Related Posts