https://www.acmicpc.net/problem/3425
3425번: 고스택
문제 고창영은 스택을 조금 변형해서 고스택을 만들었다. 고스택은 숫자만을 저장할 수 있고, 다음과 같은 10가지 연산을 수행할 수 있다. 편의상 스택의 가장 위에 저장된 수를 첫 번째 수라고 �
www.acmicpc.net
내가 다니는 회사는 알고리즘 역량을 시험으로 본다. 시험 결과를 통해 역량이 등급으로 나뉘어지는데 pro를 취득하라는 회사의 푸시가 상당하다. 그래서 매해 회사에는 여름쯤하여 스터디 그룹이 생겨났다가.. 참여율이 저조하고, 몇달 안있어 사라지는 상황이 반복되고 있다. 올해도 스터디 그룹이 생겼다. 올해는 스터디 그룹원들에게 알려줘야 하는 입장이 되는 바람에... 좀 열심히 해야하는 이유가 생겼다.
이번문제는 특별히 알고리즘적 지식이 필요하기 보단 구현력이 필요한 문제다. 미처 예상하지 못하는 꽤 많은 코너케이스들이 존재한다. 몇개 유의해야할 코너케이스들은 다음과 같다.
- 10억이 넘어가는 값을 에러처리 해야하는데 음수값도 생각해야 한다.
- 10 가까이 되는 두 값을 곱하게 될시에 integer 타입으로는 해당 값을 온전히 담지 못한다.
- DIV, MOD 연산시 해당 결과가 제수 피제수의 음수 여부 등을 문제에서 설명하고 있는데, 이부분은 일반적인 프로그래밍 언어들이 제공하는 /, % 연산이 문제가 설명한 대로 결과를 내주므로 크게 신경쓸 부분은 아니다.
- DIV, MOD 연산시 0으로 나누는 경우에 대한 예외 처리가 필요하다.
이정도를 유의하면 나머지는 구현력에 달린 것 같다. 코드 중간의 print_stack();의 주석을 풀면 해당 문제의 스텍이 변화하는 과정을 확인할 수 있다.
#include <stdio.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
typedef enum _operation
{
NUM = 1,
POP,
INV,
DUP,
SWP,
ADD,
SUB,
MUL,
DIV,
MOD
} operation;
typedef struct _instruction
{
operation opr;
long long num;
} instruction;
long long stack[100010];
instruction ins_set[100010];
int ins_count = 0;
int stack_count = 0;
int simulate(int ins_num)
{
int isError = FALSE;
switch (ins_set[ins_num].opr)
{
case NUM:
stack[stack_count] = ins_set[ins_num].num;
stack_count += 1;
break;
case POP:
if (stack_count == 0)
{
isError = TRUE;
}
else
{
stack_count -= 1;
}
break;
case INV:
if (stack_count == 0)
{
isError = TRUE;
}
else
{
stack[stack_count-1] = 0 - stack[stack_count-1];
}
break;
case DUP:
if (stack_count == 0)
{
isError = TRUE;
}
else
{
stack[stack_count] = stack[stack_count - 1];
stack_count += 1;
}
break;
case SWP:
if (stack_count < 2)
{
isError = TRUE;
}
else
{
long long temp = stack[stack_count - 1];
stack[stack_count - 1] = stack[stack_count - 2];
stack[stack_count - 2] = temp;
}
break;
case ADD:
if (stack_count < 2)
{
isError = TRUE;
}
else
{
stack[stack_count - 2] += stack[stack_count - 1];
stack_count -= 1;
}
break;
case SUB:
if (stack_count < 2)
{
isError = TRUE;
}
else
{
stack[stack_count - 2] -= stack[stack_count - 1];
stack_count -= 1;
}
break;
case MUL:
if (stack_count < 2)
{
isError = TRUE;
}
else
{
stack[stack_count - 2] *= stack[stack_count - 1];
stack_count -= 1;
}
break;
case DIV:
if (stack_count < 2)
{
isError = TRUE;
}
else if (stack[stack_count - 1] == 0)
{
isError = TRUE;
}
else
{
stack[stack_count - 2] /= stack[stack_count - 1];
stack_count -= 1;
}
break;
case MOD:
if (stack_count < 2)
{
isError = TRUE;
}
else if (stack[stack_count - 1] == 0)
{
isError = TRUE;
}
else
{
stack[stack_count - 2] %= stack[stack_count - 1];
stack_count -= 1;
}
break;
default:
break;
}
if (stack[stack_count - 1] > 1000000000 || stack[stack_count - 1] < -1000000000)
{
isError = TRUE;
}
return isError;
}
void print_stack(){
printf("%d [", stack_count);
for(int i=0; i<stack_count; ++i){
printf("%lld ", stack[i]);
}
printf("]\n");
}
int main()
{
char input[100];
int test_count;
while (1)
{
scanf("%s", input);
if (strcmp("END", input) == 0)
{
scanf("%d", &test_count);
for (int i = 0; i < test_count; ++i)
{
int isError = 0;
scanf("%lld", &(stack[0]));
stack_count = 1;
for (int j = 0; j < ins_count; ++j)
{
isError = simulate(j);
// print_stack();
if (isError == TRUE)
{
break;
}
}
if (stack_count == 1 && isError != TRUE)
{
printf("%lld\n", stack[0]);
}
else
{
printf("ERROR\n");
}
}
printf("\n");
ins_count = 0;
}
if (strcmp("QUIT", input) == 0)
{
break;
}
if (strcmp("NUM", input) == 0)
{
ins_set[ins_count].opr = NUM;
int temp;
scanf("%d", &temp);
ins_set[ins_count].num = temp;
ins_count += 1;
}
if (strcmp("POP", input) == 0)
{
ins_set[ins_count].opr = POP;
ins_count += 1;
}
if (strcmp("INV", input) == 0)
{
ins_set[ins_count].opr = INV;
ins_count += 1;
}
if (strcmp("DUP", input) == 0)
{
ins_set[ins_count].opr = DUP;
ins_count += 1;
}
if (strcmp("SWP", input) == 0)
{
ins_set[ins_count].opr = SWP;
ins_count += 1;
}
if (strcmp("ADD", input) == 0)
{
ins_set[ins_count].opr = ADD;
ins_count += 1;
}
if (strcmp("SUB", input) == 0)
{
ins_set[ins_count].opr = SUB;
ins_count += 1;
}
if (strcmp("MUL", input) == 0)
{
ins_set[ins_count].opr = MUL;
ins_count += 1;
}
if (strcmp("DIV", input) == 0)
{
ins_set[ins_count].opr = DIV;
ins_count += 1;
}
if (strcmp("MOD", input) == 0)
{
ins_set[ins_count].opr = MOD;
ins_count += 1;
}
}
return 0;
}