2023-08-02-gostack-3425

toc {:toc}

문제

고창영은 스택을 조금 변형해서 고스택을 만들었다.

고스택은 숫자만을 저장할 수 있고, 다음과 같은 10 가지 연산을 수행할 수 있다.

편의상 스택의 가장 위에 저장된 수를 첫 번째 수라고 하고, 그 다음은 차례대로 두 번째 수, 세 번째 수라고 한다.

NUM X: X 를 스택의 가장 위에 저장한다. (0 ≤ X ≤ 109)
POP: 스택 가장 위의 숫자를 제거한다.
INV: 첫 번째 수의 부호를 바꾼다. (42 → -42)
DUP: 첫 번째 숫자를 하나 더 스택의 가장 위에 저장한다.
SWP: 첫 번째 숫자와 두 번째 숫자의 위치를 서로 바꾼다.
ADD: 첫 번째 숫자와 두 번째 숫자를 더한다.
SUB: 첫 번째 숫자와 두 번째 숫자를 뺀다. (두 번째 - 첫 번째)
MUL: 첫 번째 숫자와 두 번째 숫자를 곱한다.
DIV: 첫 번째 숫자로 두 번째 숫자를 나눈 몫을 저장한다. 두 번째 숫자가 피제수, 첫 번째 숫자가 제수이다.
MOD: 첫 번째 숫자로 두 번째 숫자를 나눈 나머지를 저장한다. 두 번째 숫자가 피제수, 첫 번째 숫자가 제수이다.

이항 연산자의 경우에 첫 번째 숫자가 오른쪽에 있는 수이고, 두 번째 숫자가 왼쪽에 있는 수이다. 또, 연산을 수행하기 전에 두 숫자를 모두 스택에서 제거한 뒤, 결과를 다시 스택에 저장하는 것이다.

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

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

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

입력

입력은 기계 여러 대의 설명으로 이루어져 있다. 각 기계의 설명은 프로그램과 입력영역으로 나누어져 있다.

프로그램은 명령어로 이루어져 있고, 명령어는 한 줄에 하나씩 있다. 각 명령은 문제 설명에 나와있는 대문자 알파벳 3 글자이고, 다른 글자는 주어지지 않는다. NUM 의 경우에는 명령어 다음에 숫자가 주어지며, 이 숫자는 0 보다 크거나 같고, 109 보다 작거나 같은 정수이다. NUM 과 숫자는 공백으로 구분되어져 있다. 각 프로그램은 END 가 나오면 끝난다.

입력영역은 첫째 줄에 프로그램 수행 횟수 N 이 있다. (0 ≤ N ≤ 10,000) 다음 N 개의 줄에는 한 줄에 하나씩 입력값 Vi 가 있다. (0 ≤ Vi ≤ 109) 각 입력값에 대해서 프로그램을 한 번씩 수행해야 하고, 이 수행은 모두 독립적이다. 매번 프로그램을 수행할 때, 스택에 들어있는 값은 입력값 Vi 하나이다.

각각의 기계 설명은 빈 줄로 구분되어져 있다. QUIT 이 나오면 다음 기계 설명이 없다는 뜻이다. 명령어가 100,000 개를 넘어가는 경우와 스택이 수행될 때, 1,000 개 이상의 숫자를 저장하는 경우는 없다.

출력

각각의 입력값에 대해서, 해당하는 프로그램을 수행한 뒤, 출력값을 출력하면 된다. 출력값이란 스택에 저장되어 있는 숫자이다.

만약, 프로그램 에러가 발생하거나, 모든 수행이 종료됐을 때 스택에 저장되어 있는 숫자가 1 개가 아니라면, “ERROR” 를 출력한다.

각 기계에 대한 출력값을 모두 출력한 뒤에는 빈 줄을 하나 출력해야 한다.

풀이

조건이 여러 가지로 상당히 많지만 생각없이 무작정 달려들어 코드부터 작성했다. 결국 결과는 디버깅에만 4~5 시간은 쓴 것 같다. 전체적으로 조건을 확인한 후, 전체적인 틀을 구상하고 접근할 필요가 있다.

고스택의 동작 부분
- 첫 번째, 두 번째 수를 사용하는 경우 순서에 유의한다.
- ERROR 조건에 유의한다. (스택이 비어있는 경우, 2 개의 수를 이용하는데 스택에 1 개의 값만 있는 경우)
main 부분
- QUIT 하기 전 여러 프로그램 명령어 뭉치를 사용하기 때문에 각 스택, 벡터, error 변수를 초기화해줘야 한다.
- ERROR 조건에 유의한다. (스택에 저장된 숫자가 1 개가 아닐 때, 프로그램 에러가 발생하면 break)

long long 적용에 있어 사용되는 자료형을 전부 확인해봐야 한다. 아니면 고생한다…

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000000
typedef long long LL;
stack<LL> st;
 
bool num(LL x){
    st.push(x);
    return false;
}
 
bool pop(){
    // 스택에 아무것도 없을 때
    if (st.empty()) return true;
 
    st.pop();
    return false;
}
 
bool inv(){
    // 스택에 아무것도 없을 때
    if (st.empty()) return true;
 
    int temp;
    temp = -st.top();
    st.pop();
    st.push(temp);
    return false;
}
 
bool dup(){
    if (st.empty()) return true;
    int temp;
    temp = st.top();
    st.push(temp);
    return false;
}
 
bool swp(){
    if (st.size() < 2) return true;
    int fst, snd;
    fst = st.top();
    st.pop();
    snd = st.top();
    st.pop();
    st.push(fst);
    st.push(snd);
    return false;
}
bool add(){
    if (st.size() < 2) return true;
    LL temp, fst, snd;
    fst = st.top();
    st.pop();
    snd = st.top();
    st.pop();
    temp = fst + snd;
    st.push(temp);
    return false;
}
bool sub(){
    if (st.size() < 2) return true;
    LL temp, fst, snd;
    fst = st.top();
    st.pop();
    snd = st.top();
    st.pop();
    temp = snd-fst;
    st.push(temp);
    return false;
}
bool mul(){
    if (st.size() < 2) return true;
    LL temp, fst, snd;
    fst = st.top();
    st.pop();
    snd = st.top();
    st.pop();
    temp = snd*fst;
 
    st.push(temp);
    return false;
}
bool div(){
    if (st.size() < 2) return true;
    LL temp, fst, snd;
    bool minus = false;
    fst = st.top();
    st.pop();
    snd = st.top();
    st.pop();
    if (fst == 0) return true;
 
    // 음수일 때 연산 조건 추가
    if ((snd > 0 && fst < 0) || (snd < 0 && fst > 0)) minus = true;
    temp = abs(snd) / abs(fst);
    if (minus == true) temp = -temp;
    st.push(temp);
    return false;
}
bool mod(){
    if (st.size() < 2) return true;
    LL temp, fst, snd;
    bool minus = false;
    fst = st.top();
    st.pop();
    snd = st.top();
    st.pop();
    if (fst == 0) return true;
    
    if (snd < 0) minus = true;
    temp = abs(snd) % abs(fst);
    if (minus == true) temp = -temp;
    st.push(temp);
    return false;
}
 
int main(){
    LL n, val, cnt = 0;
    bool error;
    string str;
    vector<string> cmd;
    vector<int> n_val;
 
 
    while(true){
        error = false;
        cmd.clear();
        n_val.clear();
        while(true){
            cin >> str;
            if (str == "NUM") {
                cin >> val;
                n_val.push_back(val);
            }
            else if (str == "QUIT") {
                return 0;
            }
            else if (str == "END") {
                break;
            }
            cmd.push_back(str);
        }
        cin >> n;
 
        while(n--){
            cnt = 0;
            cin >> val;
            st.push(val);
            
            for(int i=0; i<cmd.size(); i++){
                if (cmd[i] == "NUM") error = num(n_val[cnt++]);
                else if (cmd[i] == "POP") error = pop();
                else if (cmd[i] == "INV") error = inv();
                else if (cmd[i] == "DUP") error = dup();
                else if (cmd[i] == "SWP") error = swp();
                else if (cmd[i] == "ADD") error = add();
                else if (cmd[i] == "SUB") error = sub();
                else if (cmd[i] == "MUL") error = mul();
                else if (cmd[i] == "DIV") error = div();
                else if (cmd[i] == "MOD") error = mod();
 
                if (!st.empty() && (st.top() > MAX || st.top() < -MAX))
                    error = true;
                
                if (error) break;
            }
            
            if ((st.size() == 1) && error == false) {
                cout << st.top() << endl;
            }
            else {
                cout << "ERROR" << endl;
            }
            while(!st.empty()) {
                st.pop();
            }
            
        }
        cout << endl;
    }
 
    return 0;
}

오답노트

다음의 계산 결과값의 절댓값이 1e9 보다 큰 경우를 각 동작 함수에 넣을 경우

if (!st.empty() && (st.top() > MAX || st.top() < -MAX))
    error = true;

함수 형태로 받지 않고 stack.push 로 처리하는 경우

if (cmd[i] == "NUM") error = num(n_val[cnt++]);
->
if (cmd[i] == “NUM”) st.push(n_val[cnt++]);

참고문헌

BOJ 3425 고스택

🖥️ Techtellus

Explorer

2023-08-02-gostack-3425

문제

입력

출력

풀이

오답노트

참고문헌

연결문서

Graph View

Table of Contents