BOJ
BOJ::3425 고스택
BOJ Gold 2
BOJ::3425 고스택
- Level : Gold 2
시사점
- 시뮬레이션문제로써, 빡빡하게 경우의 수를 나눠 표현하는 것이 문제가 원하는 바라고 생각합니다.
- 현재 올려놓은 코드로는 33%에서 틀렸습니다가 뜨는 상태이고, 아직 이유를 찾지 못했습니다.
- 찾지 못하였던 문제점을 찾아서 수정된 코드를 올립니다.
- 디버깅을 위해 해당 문제 출처인 CERC 2011 j번의 테스트 케이스를 사용하였습니다.
이해(20)
- 문제 이해가 쉽지 않았습니다.
- 요약하자면, 프로그램 부분과 입력 부분이있습니다.
- 프로그램 부분은 명령어들로 이루어져있습니다.
- 즉, 프로그램에 포함된 명령어들을 미리 저장해두고
- 각 입력마다 프로그램 하나를 실행시킨다고 생각하면 좋을 것 같습니다.
설계(x)
- 최대한 깔끔하게 풀어보고자, 명령어를 3가지 타입으로 나누어 구현하였습니다.
- stack_size가 2이상 필요한 경우, 1이상 필요한 경우, 그 외의 경우로 나누어 구현하였습니다.
- 추가로, (min,max), (stack_size) 등의 예외처리를 하였습니다.
시간 복잡도
공간 복잡도
구현(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)
- 실수 1 : solve 에서 실패한 경우 ret = -1로 사용했었음.(음수 -1이 stack[top]인 경우 겹친다.)
- 실수 2 : my_strcmp를 생성할때 비교 자료형에 const를 붙여주지 않으면 compile이 되지 않습니다.
- 실수 3 : int형 자료형 A, B, C가 있고, C = A * B 일때,
- 계산 결과인 C가 overflow가 나는지 안나는지는 int형 자료형 C로 알 수 없습니다.
- 예를 들어 해당 문제에서 A와 B가 1040204인 경우,
- c 는 1.0821^10 이 됩니다.
- 따라서 overflow가 나고도 한 바퀴 돌아서 -3만 얼마정도가 C가 됩니다.
- 이때 우리가 c를 mn과 mx 사이의 범위에 들어있는지 확인해도 이미 늦습니다.
- 해당 문제를 해결하기 위해 long long으로 모두 변경하여 사용하였습니다.
문제에 나온 정수형의 범위와 해당 정수형을 문제에 주어진 어떤 연산을 했을때 결과값의 범위를 체크하는 것은 가장 중요한 일이라고 할 수 있겠습니다.
2nd try
- (12m) : switch-case문 내에서는 변수를 선언할 수 없다는 사실을 처음 알았습니다.
- (23m) : 연산 결과가 10^9 보다 큰지 체크는 했지만, -10^9보다 작은지는 체크 하지 않았습니다.