Life Engineering
[BOJ 3425] 고스택(C++) 본문
삼성SDS 알고리즘 특강에서 1번째로 풀이해줬던 문제..
난 제한시간안에 못풀었다 ㅜㅜ
https://www.acmicpc.net/problem/3425
3425번: 고스택
각각의 입력값에 대해서, 해당하는 프로그램을 수행한 뒤, 출력값을 출력하면 된다. 출력값이란 스택에 저장되어 있는 숫자이다. 만약, 프로그램 에러가 발생하거나, 모든 수행이 종료됐을 때
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
|
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#define MAX 1000000000
#define ll long long
using namespace std;
typedef struct Instruction{
string inst;
ll num;
} Instruction;
Instruction makeInstruction(string s, ll num){
Instruction i;
i.inst=s;
i.num=num;
return i;
}
bool NUM(stack<long>& s, ll num){
s.push(num);
return true;
}
bool POP(stack<long> &s){
if (s.empty()){
return false;
}
s.pop();
return true;
}
bool INV(stack<long> &s){
if (s.empty()){
return false;
}
ll n=s.top();
s.pop();
s.push(-n);
return true;
}
bool DUP(stack<long> &s){
if (s.empty()){
return false;
}
s.push(s.top());
return true;
}
bool SWP(stack<long> &s){
if (s.size()<2){
return false;
}
ll a=s.top();
s.pop();
ll b=s.top();
s.pop();
s.push(a);
s.push(b);
return true;
}
bool ADD(stack<long> &s){
if (s.size()<2){
return false;
}
ll first=s.top();
s.pop();
ll second=s.top();
s.pop();
s.push(first+second);
return true;
}
bool SUB(stack<long> &s){
if (s.size()<2){
return false;
}
ll first=s.top();
s.pop();
ll second=s.top();
s.pop();
s.push(second-first);
return true;
}
bool MUL(stack<long> &s){
if (s.size()<2){
return false;
}
ll first=s.top();
s.pop();
ll second=s.top();
s.pop();
s.push(second*first);
return true;
}
bool DIV(stack<long> &s){
if (s.size()<2){
return false;
}
ll first=s.top();
if (first==0){
return false;
}
s.pop();
ll second=s.top();
s.pop();
s.push(second/first);
return true;
}
bool MOD(stack<long> &s){
if (s.size()<2){
return false;
}
ll first=s.top();
if (first==0){
return false;
}
s.pop();
ll second=s.top();
s.pop();
s.push(second%first);
return true;
}
int main(void){
string input;
ll n, num_input;
int cnt;
vector<Instruction> inst_list;
while(true){
inst_list.clear();
while(true){
cin>>input;
if (input=="QUIT"){
return 0;
}
if (input=="END"){
break;
}
if (input=="NUM"){
cin>>n;
inst_list.push_back(makeInstruction(input,n));
}
else{
inst_list.push_back(makeInstruction(input, 0));
}
}
cin>>cnt;
while (cnt--){
bool flag=true;
stack<long> s;
cin>>num_input;
s.push(num_input);
for (int i=0; i<inst_list.size(); i++){
if (inst_list[i].inst=="NUM"){
flag=NUM(s,inst_list[i].num);
}
else if (inst_list[i].inst=="POP"){
flag=POP(s);
}
else if (inst_list[i].inst=="INV"){
flag=INV(s);
}
else if (inst_list[i].inst=="DUP"){
flag=DUP(s);
}
else if (inst_list[i].inst=="SWP"){
flag=SWP(s);
}
else if (inst_list[i].inst=="ADD"){
flag=ADD(s);
}
else if (inst_list[i].inst=="SUB"){
flag=SUB(s);
}
else if (inst_list[i].inst=="MUL"){
flag=MUL(s);
}
else if (inst_list[i].inst=="DIV"){
flag=DIV(s);
}
else if (inst_list[i].inst=="MOD"){
flag=MOD(s);
}
if (!s.empty() && abs(s.top())>MAX){
flag=false;
}
if (!flag){
break;
}
}
if (s.size()!=1){
flag=false;
}
if (!flag){
cout<<"ERROR"<<endl;
}
else{
cout<<s.top()<<endl;
}
}
cout<<"\n";
}
}
|
cs |
구현 능력이 포인트인 문제다.
처음에 입력받는 부분부터 헤맸다.
일단 명령어 instruction, number를 가지는 struct를 선언하고 그를 구성하는 vector를 만든다.
END가 나오면 명령어 받기를 종료하고 반복문을 빠져나와 n번만큼 while문을 돌며, 아까 저장한 명령문 리스트를 참조하여 스택을 연산한다.
이 두 줄 아이디어를 구현하기가 쉽지 않았다. 또한 flag값을 주어 에러 체크를 할 수 있도록 한다.