링크 : https://www.acmicpc.net/problem/3425
3425번: 고스택
문제 고창영은 스택을 조금 변형해서 고스택을 만들었다. 고스택은 숫자만을 저장할 수 있고, 다음과 같은 10가지 연산을 수행할 수 있다. 편의상 스택의 가장 위에 저장된 수를 첫 번째 수라고
www.acmicpc.net
문제 설명 :
더보기
고스택은 숫자만을 저장할 수 있고, 다음과 같은 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"를 출력한다.
각 기계에 대한 출력값을 모두 출력한 뒤에는 빈 줄을 하나 출력해야 한다.
예제 입력 :
더보기
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
예제 출력 :
더보기
3 102 2502 ERROR ERROR 600000000 ERROR 600000001
접근법 :
1) 어떻게 풀 것인가?
문제 처음부터 NUM X, POP, INV 등 10개의 기능을 구현해달라고 한다.
각 기능은 단순하며, STACK 자료구조에서 기본적으로 제공하는 기능에 몇개를 추가한 형태이다.
즉, 특별한 알고리즘이 필요한 문제가 아니라 주어진 조건을 그대로 구현할 수 있는지에 대한 문제이다.
2) 시간복잡도
명령어 최대 100,000개, N 최대 10,000개로 시간복잡도 최대 10억이 소요되나 단순 연산이므로 무리없어보인다.
(실제 실행시간 : C 4ms)
3) 공간복잡도
STACK 최대 크기 long long 1,000개 (다 풀고 보니 연산의 결과값이 10^19를 넘으면 안되므로 int로도 가능)
= 8,000 Bytes
명령어 int로 할 경우에도 100,000개 = 약 390Kbytes
등 아무리 넉넉히 잡아도 128MB 제한에 충분.
4) 풀면서 놓쳤던점
- 시간초과가 나서 확인해보니 freopen("input.txt", "r", stdin); 을 주석처리 하지 않고 제출했다.
- 10^19 초과할 경우 예외처리 했어야하는데, 10^19 이상일 경우 예외처리했다
-> 문제 발생시 입출력, 초과/이상 확인 먼저하는 것을 다시 한 번 숙지해야겠다.
5) 이 문제를 통해 얻어갈 것
삼성 SW역량테스트 B형, C형은 라이브러리 사용이 불가하며, 이 문제처럼 기본적인 자료구조와 함수를 다 구현해야한다. 비록 난이도의 차이는 크지만 이렇게 기본적인 자료구조부터 차근차근 구현할 수 있는 연습을 해두면 좋을 것 같다.
Ex> Merge sort, malloc 등
Java 코드 :
import java.io.*;
import java.util.*;
public class Main {
private static final int MAX_STACK_SIZE = 1001;
private static final int MAX_CMD_SIZE = 100001;
private static final int MAX_VALUE = 1000000000;
static long[] stack = new long[MAX_STACK_SIZE];
static int pt = 0;
// 1 numX 2 pop 3 inv 4 dup 5 swp 6 add 7 sub 8 mul 9 div 10 mod
static int[] cmdArray = new int [MAX_CMD_SIZE];
static int cmdPt = 0;
// num X 배열
static ArrayList<Integer> numxArray = new ArrayList<Integer>();
static int numxPt = 0;
static boolean quitFlag = false;
static boolean errorFlag = false;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (;;) {
// 1. 커맨드 입력
// ** 초기화
cmdPt = pt = 0;
numxArray = new ArrayList<Integer>();
String inputStr;
while(true) {
inputStr = br.readLine();
// 1) 탈출조건 먼저 처리
if (inputStr.equals("QUIT")) {
quitFlag = true;
break;
}
else if (inputStr.equals("END")) {
break;
}
// 2) 명령어 배열에 넣기
// 1 num / 2 pop / 3 inv / 4 dup / 5 swp / 6 add / 7 sub / 8 mul / 9 div / 10 mod
String[] inStrList = inputStr.split(" ");
inputStr = inStrList[0];
if (inputStr.equals("NUM")) {
cmdArray[cmdPt] = 1;
cmdPt++;
int x = Integer.parseInt(inStrList[1]);
numxArray.add(x);
}
else if (inputStr.equals("POP")) {
cmdArray[cmdPt++] = 2;
}
else if (inputStr.equals("INV")) {
cmdArray[cmdPt++] = 3;
}
else if (inputStr.equals("DUP")) {
cmdArray[cmdPt++] = 4;
}
else if (inputStr.equals("SWP")) {
cmdArray[cmdPt++] = 5;
}
else if (inputStr.equals("ADD")) {
cmdArray[cmdPt++] = 6;
}
else if (inputStr.equals("SUB")) {
cmdArray[cmdPt++] = 7;
}
else if (inputStr.equals("MUL")) {
cmdArray[cmdPt++] = 8;
}
else if (inputStr.equals("DIV")) {
cmdArray[cmdPt++] = 9;
}
else if (inputStr.equals("MOD")) {
cmdArray[cmdPt++] = 10;
}
}
// 2. 종료 조건
if (quitFlag == true) {
bw.write(sb.toString());
break;
}
// 3. 고스택 구현부
int N = Integer.parseInt(br.readLine());
int inNum;
for (int i = 0; i<N; i++) {
// ** 초기화
errorFlag = false;
numxPt = pt = 0;
inNum = Integer.parseInt(br.readLine());
stack[pt++] = inNum;
goStack();
}
sb.append("\n");
}
br.close();
bw.close();
return;
}
// 3. 고스택 구현부
static void goStack() throws IOException {
// 1 num / 2 pop / 3 inv / 4 dup / 5 swp / 6 add / 7 sub / 8 mul / 9 div / 10 mod
int cmd;
// 1 num / 2 pop / 3 inv / 4 dup / 5 swp / 6 add / 7 sub / 8 mul / 9 div / 10 mod
for (int i = 0; i<cmdPt; i++) {
// ** 탈출조건 먼저
if (errorFlag) break;
cmd = cmdArray[i];
if (cmd == 1) {
num(numxArray.get(numxPt++));
}
else if (cmd == 2) {
if (pt==0) {
errorFlag = true;
break;
}
pop();
}
else if (cmd == 3) {
inv();
}
else if (cmd == 4) {
if (pt==0) {
errorFlag = true;
break;
}
dup();
}
else if (cmd == 5) {
if (pt<=1) {
errorFlag = true;
break;
}
swp();
}
else if (cmd == 6) {
if (pt<=1) {
errorFlag = true;
break;
}
add();
}
else if (cmd == 7) {
if (pt<=1) {
errorFlag = true;
break;
}
sub();
}
else if (cmd == 8) {
if (pt<=1) {
errorFlag = true;
break;
}
mul();
}
else if (cmd == 9) {
if (pt<=1) {
errorFlag = true;
break;
}
div();
}
else if (cmd == 10) {
if (pt<=1) {
errorFlag = true;
break;
}
mod();
}
}
if (errorFlag==true || pt != 1) {
sb.append("ERROR\n");
}
else {
sb.append(stack[0]+"\n");
}
}
// ↓ 각 기능별 구현 ↓
static void num(int x) {
stack[pt++] = x;
}
static void pop() {
pt--;
}
static void inv() {
stack[pt-1] = -stack[pt-1];
}
static void dup() {
stack[pt] = stack[pt-1];
pt++;
}
static void swp() {
long tmp = stack[pt - 1];
stack[pt - 1] = stack[pt - 2];
stack[pt - 2] = tmp;
}
static void add() {
long tmp = stack[pt - 1] + stack[pt - 2];
if (Math.abs(tmp) > MAX_VALUE) {
errorFlag = true;
return;
}
stack[pt - 2] = tmp;
pt--;
}
static void sub() {
long tmp = stack[pt - 2] - stack[pt - 1];
if (Math.abs(tmp) > MAX_VALUE) {
errorFlag = true;
return;
}
stack[pt - 2] = tmp;
pt--;
}
static void mul() {
long tmp = stack[pt - 2] * stack[pt - 1];
if (Math.abs(tmp) > MAX_VALUE) {
errorFlag = true;
return;
}
stack[pt - 2] = tmp;
pt--;
}
static void div() {
long tmp1, tmp2;
int tFlag = 0;
if (stack[pt - 1] == 0) {
errorFlag = true;
return;
}
tmp1 = stack[pt - 2];
tmp2 = stack[pt - 1];
if (tmp1 < 0) tFlag++;
if (tmp2 < 0) tFlag++;
tmp1 = Math.abs(tmp1) / Math.abs(tmp2);
if (tFlag == 1) stack[pt - 2] = -tmp1;
else stack[pt - 2] = tmp1;
pt--;
}
static void mod() {
long tmp;
if (stack[pt - 1] == 0) {
errorFlag = true;
return;
}
tmp = Math.abs(stack[pt - 2]) % Math.abs(stack[pt - 1]);
if (stack[pt - 2] < 0) stack[pt - 2] = -tmp;
else stack[pt - 2] = tmp;
pt--;
}
}
C 코드 :
// 고스택 3425 C++
#if 1
#pragma warning(disable:4996)
#include <stdio.h>
#define NUM (1000000000)
#define ABS(a) ((a)>0? (a) : (-a))
//using namespace std;
void numX(int x);
void pop();
void inv();
void dup();
void swp();
void add();
void sub();
void mul();
void div();
void mod();
void input();
void program();
int flag;
int x, N;
char inputStr[5];
int cmd[100001]; // 명령어 개수
int num[100001];
int inNum[10001];
// 고스택 자료구조
long long stack[1002];
int cPt, nPt, pt;
int main() {
//freopen("input.txt", "r", stdin);
// 탈출조건 나올때까지 무한 반복
while(1){
// 1. 입력
input();
// ** QUIT 나오면 프로그램 종료
if (flag == -1) return 0;
// 2. 구현부
program();
}
return 0;
}
void input() {
flag = cPt = nPt = 0;
while(1) {
scanf("%s", &inputStr[0]);
// flag 값 설정
// NUM 0 / POP 1 / INV 2 / DUP 3 / DIV 4 / SWP 5 / SUB 6 / ADD 7
// MUL 8 / MOD 9 / END break / QUIT -1 / ERROR -2
if (inputStr[0] == 'N') {
scanf("%d", &x);
cmd[cPt++] = 0;
num[nPt++] = x;
}
else if (inputStr[0] == 'P') cmd[cPt++] = 1;
else if (inputStr[0] == 'I') cmd[cPt++] = 2;
else if (inputStr[0] == 'D') {
if (inputStr[1] == 'U') cmd[cPt++] = 3;
else cmd[cPt++] = 4;
}
else if (inputStr[0] == 'S') {
if (inputStr[1] == 'W') cmd[cPt++] = 5;
else cmd[cPt++] = 6;
}
else if (inputStr[0] == 'A') cmd[cPt++] = 7;
else if (inputStr[0] == 'M') {
if (inputStr[1] == 'U') cmd[cPt++] = 8;
else cmd[cPt++] = 9;
}
else if (inputStr[0] == 'E') break;
else if (inputStr[0] == 'Q') {
flag = -1;
return;
}
}
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
scanf("%d", &inNum[i]);
}
}
void program() {
for (int i = 1; i <= N; i++) {
nPt = pt = 0;
stack[pt++] = inNum[i];
for (int j = 0; j < cPt; j++) {
flag = cmd[j];
// flag 값 설정
// NUM 0 / POP 1 / INV 2 / DUP 3 / DIV 4 / SWP 5 / SUB 6 / ADD 7
// MUL 8 / MOD 9 / END break / QUIT -1 / ERROR -2
if (flag == 0) { // NUM
numX(num[nPt++]);
}
else if (flag == 2) { // INV
inv();
}
else if (pt == 0) {
flag = -2;
break;
}
else if (flag == 1) { // POP
pop();
}
else if (flag == 3) { // DUP
dup();
}
else if (pt == 1) {
flag = -2;
break;
}
else if (flag == 4) { // DIV
div();
}
else if (flag == 5) { // SWP
swp();
}
else if (flag == 6) { // SUB
sub();
}
else if (flag == 7) { // ADD
add();
}
else if (flag == 8) { // MUL
mul();
}
else if (flag == 9) { // MOD
mod();
}
if (flag == -2) break;
}
if (flag == -2 || pt != 1) printf("ERROR\n");
else printf("%lld\n", stack[0]);
}
printf("\n");
}
void numX(int x) {
stack[pt++] = x;
}
void pop() {
pt--;
}
void inv() {
stack[pt - 1] = -stack[pt - 1];
}
void dup() {
stack[pt++] = stack[pt - 1];
}
void swp() {
long long tmp = stack[pt - 1];
stack[pt - 1] = stack[pt - 2];
stack[pt - 2] = tmp;
}
void add() {
long long tmp = stack[pt - 1] + stack[pt - 2];
if (ABS(tmp) > NUM) {
flag = -2;
return;
}
stack[pt - 2] = tmp;
pt--;
}
void sub() {
long long tmp = stack[pt - 2] - stack[pt - 1];
if (ABS(tmp) > NUM) {
flag = -2;
return;
}
stack[pt - 2] = tmp;
pt--;
}
void mul() {
long long tmp = stack[pt - 2] * stack[pt - 1];
if (ABS(tmp) > NUM) {
flag = -2;
return;
}
stack[pt - 2] = tmp;
pt--;
}
void div() {
long long tmp1, tmp2;
int tFlag = 0;
if (stack[pt - 1] == 0) {
flag = -2;
return;
}
tmp1 = stack[pt - 2];
tmp2 = stack[pt - 1];
if (tmp1 < 0) tFlag++;
if (tmp2 < 0) tFlag++;
tmp1 = ABS(tmp1) / ABS(tmp2);
if (tFlag == 1) stack[pt - 2] = -tmp1;
else stack[pt - 2] = tmp1;
pt--;
}
void mod() {
long long tmp;
if (stack[pt - 1] == 0) {
flag = -2;
return;
}
tmp = ABS(stack[pt - 2]) % ABS(stack[pt - 1]);
if (stack[pt - 2] < 0) stack[pt - 2] = -tmp;
else stack[pt - 2] = tmp;
pt--;
}
#endif
C++ 코드 (kskim90 님 코드) :
#include <cstdio>
#define MAX_O 100000
#define SZ_STK 1000
#define LIMIT 1000000000
typedef long long ll;
struct Stk {
int arr[SZ_STK];
int idx;
void init(const int& n) {
arr[idx = 0] = n;
}
int size() {
return idx + 1;
}
int top() { return arr[idx]; }
int abs(const int& a) { return (a < 0) ? -a: a; }
ll abs(const ll& a) { return (a < 0) ? -a: a; }
bool num(const int& n) {
arr[++idx] = n;
return true;
}
bool pop() { return (idx-- >= 0); }
bool inv() {
if (idx < 0) return false;
arr[idx] *= -1;
return true;
}
bool dup() {
if (idx < 0) return false;
arr[idx + 1] = arr[idx];
++idx;
return true;
}
bool swp() {
if (idx < 1) return false;
int t = arr[idx];
arr[idx] = arr[idx - 1];
arr[idx - 1] = t;
return true;
}
bool add() {
if (idx < 1) return false;
arr[idx - 1] += arr[idx];
return abs(arr[--idx]) <= LIMIT;
}
bool sub() {
if (idx < 1) return false;
arr[idx - 1] -= arr[idx];
return abs(arr[--idx]) <= LIMIT;
}
bool mul() {
if (idx < 1) return false;
ll t = (ll)arr[idx] * arr[idx - 1];
if (abs(t) > LIMIT) return false;
arr[--idx] = t;
return true;
}
bool div() {
if (idx < 1 || arr[idx] == 0) return false;
arr[idx - 1] /= arr[idx];
--idx;
return true;
}
bool mod() {
if (idx < 1 || arr[idx] == 0) return false;
arr[idx - 1] %= arr[idx];
--idx;
return true;
}
} stk;
struct Ord {
int tp;
int n;
} ords[MAX_O];
int main() {
char o[4];
int i, O, N, n;
bool flag;
while (true) {
scanf("%s", o);
if (o[0] == 'Q') break;
O = 0;
while (o[0] != 'E') {
if (o[0] == 'N') scanf("%d", &n), ords[O].tp = 0, ords[O++].n = n;
else if (o[0] == 'P') ords[O++].tp = 1;
else if (o[0] == 'I') ords[O++].tp = 2;
else if (o[0] == 'D' && o[1] == 'U') ords[O++].tp = 3;
else if (o[0] == 'S' && o[1] == 'W') ords[O++].tp = 4;
else if (o[0] == 'A') ords[O++].tp = 5;
else if (o[0] == 'S') ords[O++].tp = 6;
else if (o[0] == 'M' && o[1] == 'U') ords[O++].tp = 7;
else if (o[0] == 'D') ords[O++].tp = 8;
else ords[O++].tp = 9;
scanf("%s", o);
}
scanf("%d", &N);
while (--N >= 0) {
scanf("%d", &n);
stk.init(n);
flag = true;
for (i = 0; i < O; ++i) {
if (ords[i].tp == 0) flag = stk.num(ords[i].n);
else if (ords[i].tp == 1) flag = stk.pop();
else if (ords[i].tp == 2) flag = stk.inv();
else if (ords[i].tp == 3) flag = stk.dup();
else if (ords[i].tp == 4) flag = stk.swp();
else if (ords[i].tp == 5) flag = stk.add();
else if (ords[i].tp == 6) flag = stk.sub();
else if (ords[i].tp == 7) flag = stk.mul();
else if (ords[i].tp == 8) flag = stk.div();
else flag = stk.mod();
if (!flag) break;
}
if (!flag || stk.size() != 1) printf("ERROR\n");
else printf("%d\n", stk.top());
}
printf("\n");
}
return 0;
}반응형
'알고리즘 Algorithm > BOJ 백준 (초급~중급)' 카테고리의 다른 글
| [BOJ 백준] 수찾기(1920) Java (2) | 2020.06.29 |
|---|---|
| [BOJ 백준] 교환(1039) Java (0) | 2020.06.28 |
| [BOJ 백준] 게임(1103) Java (2) | 2020.06.26 |
| [BOJ 백준] 가르침(1062) Java (0) | 2020.06.23 |
| [BOJ 백준] 탈출(3055) Java (0) | 2020.06.23 |