[백준] 3425번 고스택 (C++)
문제
고창영은 스택을 조금 변형해서 고스택을 만들었다. 고스택은 숫자만을 저장할 수 있고, 다음과 같은 10가지 연산을 수행할 수 있다.
- NUM X: X를 스택의 가장 위에 저장한다. (0 ≤ X ≤ 109)
- POP: 스택 가장 위의 숫자를 제거한다.
- INV: 첫 번째 수의 부호를 바꾼다. (42 -> -42)
- DUP: 첫 번째 숫자를 하나 더 스택의 가장 위에 저장한다.
- SWP: 첫 번째 숫자와 두 번째 숫자의 위치를 서로 바꾼다.
- ADD: 첫 번째 숫자와 두 번째 숫자를 더한다.
- SUB: 첫 번째 숫자와 두 번째 숫자를 뺀다. (두 번째 - 첫 번째)
- MUL: 첫 번째 숫자와 두 번째 숫자를 곱한다.
- DIV: 첫 번째 숫자로 두 번째 숫자를 나눈다. (두 번째 / 첫 번째)
- MOD: 첫 번째 숫자로 두 번째 숫자를 나눈 나머지를 저장한다. (두 번째 % 첫 번째)
입력
입력은 프로그램 여러 개로 이루어져 있다. 각 프로그램은 명령어가 한 줄에 하나씩 주어지며, “END”를 만나면 이 프로그램이 끝난다. 그 다음 줄에는 프로그램의 입력 개수 N이 주어진다. 다음 N개의 줄에는 프로그램의 입력이 한 줄에 하나씩 주어진다. 각 프로그램의 입력은 0이상 109이하의 정수이다. 프로그램의 입력 개수는 0보다 크고 10000보다 작다. 프로그램이 “QUIT”일 경우 프로그램을 종료한다.
예제 입력 1
DUP
MUL
NUM 2
ADD
END
3
1
10
50
NUM 1
NUM 1
ADD
END
2
42
43
NUM 600000000
ADD
END
3
0
600000000
1
QUIT
출력
각각의 입력에 대해서, 해당하는 프로그램을 수행한 뒤, 스택에 저장되어 있는 숫자를 출력한다. 만약, 프로그램 수행 중 다음과 같은 경우가 발생한다면, “ERROR”를 출력한다.
- 연산 수행 중 숫자가 부족한 경우
- 0으로 나눈 경우
- 연산 결과의 절댓값이 109를 넘어가는 경우
- 프로그램 종료시 스택에 저장되어 있는 숫자가 1개가 아닌 경우
예제 출력 1
3
102
2502
ERROR
ERROR
600000000
ERROR
600000001
풀이
문제 해결 방법
이 문제는 스택을 이용한 시뮬레이션 문제입니다. 주요 해결 단계는 다음과 같습니다:
- 명령어 파싱: 각 명령어를 입력받아 처리합니다.
- 스택 연산 구현: 10가지 연산을 정확히 구현합니다.
- 예외 처리:
- 스택 언더플로우
- 0으로 나누기
- 오버플로우
- 최종 결과 검증
이 알고리즘의 시간 복잡도는 각 테스트 케이스당 O(M × N)입니다. 여기서 M은 명령어의 수, N은 입력의 수입니다.
코드
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <algorithm>
int n, top;
long long st[1002];
char cmd[100002][5];
long long nums[100002];
int main()
{
int i, j;
for (;;)
{
int m;
for (m = 1;; m++)
{
scanf(" %s", cmd[m]);
if (strcmp(cmd[m], "QUIT") == 0)
{
return 0;
}
if (strcmp(cmd[m], "END") == 0)
break;
if (strcmp(cmd[m], "NUM") == 0)
{
scanf("%lld", &nums[m]);
}
}
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
scanf("%lld", &st[0]);
top = 1;
bool isError = false;
for (j = 1; j <= m; j++)
{
if (strcmp(cmd[j], "NUM") == 0) {
st[top++] = nums[j];
}
else if (strcmp(cmd[j], "POP") == 0) {
if (top < 1)
{
isError = true;
break;
}
top--;
}
else if (strcmp(cmd[j], "INV") == 0) {
if (top < 1)
{
isError = true;
break;
}
st[top - 1] = -st[top - 1];
}
else if (strcmp(cmd[j], "DUP") == 0) {
if (top < 1)
{
isError = true;
break;
}
st[top++] = st[top - 1];
}
else if (strcmp(cmd[j], "SWP") == 0) {
if (top < 2)
{
isError = true;
break;
}
std::swap(st[top - 1], st[top - 2]);
}
else if (strcmp(cmd[j], "ADD") == 0) {
if (top < 2)
{
isError = true;
break;
}
st[top - 2] += st[top - 1];
top--;
}
else if (strcmp(cmd[j], "SUB") == 0) {
if (top < 2)
{
isError = true;
break;
}
st[top - 2] -= st[top - 1];
top--;
}
else if (strcmp(cmd[j], "MUL") == 0) {
if (top < 2)
{
isError = true;
break;
}
st[top - 2] *= st[top - 1];
top--;
}
else if (strcmp(cmd[j], "DIV") == 0) {
if (top < 2 || st[top - 1] == 0)
{
isError = true;
break;
}
st[top - 2] /= st[top - 1];
top--;
}
else if (strcmp(cmd[j], "MOD") == 0) {
if (top < 2 || st[top - 1] == 0)
{
isError = true;
break;
}
st[top - 2] %= st[top - 1];
top--;
}
if (top != 0 && std::abs(st[top - 1]) > 1e9)
{
isError = true;
break;
}
}
if (top != 1 || isError)
{
printf("ERROR\n");
}
else
{
printf("%lld\n", st[0]);
}
}
printf("\n");
}
return 0;
}
댓글남기기