접기
문제에 주어진 함수들을 그대로 구현하면 해결할 수 있습니다.
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
//code by RiKang, weeklyps.com
#include < stdio.h>
typedef int node_type;
const int stack_size_max = 1000000 ;
struct DS_stack{
int stack_size= 0 ;
node_type arr[stack_size_max];
node_type top(){
if (stack_size= = 0 ) return - 1 ;
return arr[stack_size- 1 ];
}
void push(node_type v){
arr[stack_size+ + ] = v;
}
int pop (){
int ret = top();
if (stack_size! = 0 )
stack_size- - ;
return ret;
}
int empty(){
if (stack_size= = 0 ) return 1 ;
return 0 ;
}
int size (){
return stack_size;
}
};
int main() {
DS_stack st;
int t;
scanf ("%d" ,& t);
char a[15 ];
while (t- - ){
scanf ("%s" ,a);
if (a[0 ]= = 'p' & & a[1 ]= = 'u' ){ // push
int in;
scanf ("%d" ,& in);
st.push(in);
}
else if (a[0 ]= = 'p' ){ // pop
printf ("%d\n" ,st.pop ());
}
else if (a[0 ]= = 's' ){ // size
printf ("%d\n" ,st.size ());
}
else if (a[0 ]= = 'e' ){ // empty
printf ("%d\n" ,st.empty());
}
else { // top
printf ("%d\n" ,st.top());
}
}
return 0 ;
}
cs
접기 접기
스택 수열에서 pop을 할 때 k라는 숫자가 나오기 위해서는, 스택의 top에 k가 있어야 합니다. 따라서 스택 수열의 다음 숫자가 k라면, top이 k가 될 때까지 push를 해줘야 합니다. 만약 top 에 k를 넣을 수 없다면, NO를 출력합니다. 그런 경우는 k가 이미 스택 안에 있으면서 top이 아닌 경우입니다.
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
//code by RiKang, weeklyps.com
#include < stdio.h>
typedef int node_type;
const int stack_size_max = 1000005 ;
struct DS_stack{
int stack_size= 0 ;
node_type arr[stack_size_max];
node_type top(){
if (stack_size= = 0 ) return - 1 ;
return arr[stack_size- 1 ];
}
void push(node_type v){
arr[stack_size+ + ] = v;
}
void pop (){
if (stack_size! = 0 )
stack_size- - ;
}
};
int m;
char ans[1000005 ];
int main() {
DS_stack st;
int n;
scanf ("%d" ,& n);
int push_num= 0 ;
for (int i= 1 ; i< = n; i+ + ){
int in;
scanf ("%d" ,& in);
while (push_num< in){
st.push(+ + push_num);
ans[m+ + ] = '+' ;
}
if (st.top()! = in){
printf ("NO" );
return 0 ;
}
st.pop ();
ans[m+ + ] = '-' ;
}
for (int i= 0 ; i< m; i+ + )
printf ("%c\n" ,ans[i]);
return 0 ;
}
cs
접기 접기
문자열을 순서대로 보면서 '('가 나오면 push, ')'가 나오면 pop이라고 생각하면 stack과 동일한 문제임을 알 수 있습니다. 더 간단한 방법도 있지만, 여기서는 스택까지 사용하는 방법을 소개하겠습니다.
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
//code by RiKang, weeklyps.com
#include < stdio.h>
#include < string .h>
typedef char node_type;
const int stack_size_max = 1000005 ;
struct DS_stack{
int stack_size= 0 ;
node_type arr[stack_size_max];
node_type top(){
if (stack_size= = 0 ) return - 1 ;
return arr[stack_size- 1 ];
}
void push(node_type v){
arr[stack_size+ + ] = v;
}
void pop (){
if (stack_size! = 0 )
stack_size- - ;
}
};
void solve(){
DS_stack st;
char a[105 ];
bool ans = true ;
scanf ("%s" ,a);
for (int i= 0 ; i< strlen(a); i+ + ){
if (a[i]= = '(' ) st.push('(' );
else {
if (st.stack_size= = 0 ) ans = false ;
st.pop ();
}
}
ans & = st.stack_size= = 0 ;
printf ("%s\n" ,ans?"YES" :"NO" );
}
int main() {
int t;
scanf ("%d" ,& t);
while (t- - ){
solve();
}
return 0 ;
}
cs
접기