ITwork

www.acmicpc.net/problem/1874

이 문제는 여러 우여곡절 끝에 답을 찾은 문제 입니다.

for loop에 39,43 라인에 원래 cout을 사용했더니 시간초과로 정답이 안되는 문제가 있어서 여기저기 찾아보니

endl이 시간을 많이 소모해서 문제가 된다고 하여 printf로 수정했습니다. 

endl을 '\n'으로 바꾸셔도 되고 아예 printf문으로 다 바꿔도 됩니다. 

cout이 편리해서 잘 사용하고 있었는데, 이런 문제가 있네요. 참고로 하시기 바랍니다.  

아래 코드도 아직 틀렸다고 하는데 왜 틀렸는지 잘 모르겠네요. 혹시 아시는 분은 아래 답변 좀 부탁드립니다. 

cout << dtout[i] << endl;

cout << "NO" << endl;

  1 /*baekjoon 1874*/                                                                         
  2 #define _CRT_SECURE_NO_WARNINGS
  3 #include <iostream>
  4 #include <stack>
  5 #include <string.h>
  6 
  7 using namespace std;
  8 #define MAX 100001
  9 int dt[MAX];
 10 char dtout[MAX];
 11 stack<int> s;
 12 
 13 
 14 int main()
 15 {
 16     int i,j=0,k=0, n;
 17     int size;
 18 
 19     /* input size*/
 20     cin >> n;
 21 
 22     /* input data*/
 23     for(i= 0; i<n; i++ ){
 24         cin >> dt[i];
 25     }
 26 
 27     for( i=1; i <= n; i++){
 28         s.push(i);
 29         dtout[k++] = '+';
 30         while( !s.empty() && s.top() == dt[j] ){
 31             s.pop();
 32             dtout[k++] = '-';
 33             j++;
 34         }
 35     }
 36 
 37     size = strlen( dtout );
 38     if( !s.empty() ) {
 39         printf("NO");
 40         return 0;
 41     }else{
 42         for( i = 0; i< size; i++) {
 43             printf("%c\n", dtout[i]);
 44         }
 45     }
 46 
 47     return 0;
 48 }

www.acmicpc.net/problem/9012

아래 코드로 돌렸을 때 segmentation fault 발생 해서 gdb로 디버깅 한 결과입니다.

일단 은 어느 코드에서 문제가 발생한 정도로만 확인이 가능한데, 이정도만 추적을 해도 코드 수정하는데 많은 도움이 된다고 보입니다. 

  1 #include <iostream>                                                                                                                                                                                    
  2 #include <stack>
  3 #include <string.h>
  4 
  5 using namespace std;
  6 
  7 int main()
  8 {
  9     int n=0,i,j, check=0, count;
 10     char input[51];
 11 
 12     stack<char> s;
 13     cin >> count;
 14 
 15     for(j=0; j<count; j++)
 16     {
 17         check = 0;
 18         cin >> input;
 19         n = strlen(input);
 20 
 21         for(i=0; i<n; i++)
 22         {
 23             if ( input[i] == '(')
 24                 s.push(input[i]);
 25             else if(i == 0 && input[i] == ')')
 26             {
 27                 s.push(input[i]);
 28                 break;
 29             }
 30             else if( i !=0 && input[i]  == ')' )
 31             {
 32                 if( s.top() == '(' )
 33                     s.pop();
 34                 else
 35                     s.push(input[i]);
 36             }
 37         }   
 38         
 39         if( s.empty() )
 40             cout << "YES" << endl;
 41         else
 42             cout << "NO" << endl;
 43             
 44     }
 45     return 0;
 46 }   

#gdb ./a.out

gdb b main

gdb r

input값은 각각 count와 input 입력시 넣어 주시면 됩니다. 

1 <-- count

(())()) <-- input

step을 해보면서 segmentation fault발생한 지점이 32 line s.top()에서 문제가 발생한 것을 알았으며

s.top()이 stack에  아무것도 없을 경우 값이 이상한 값을 return하므로 조건문을 s.empty()인지를 추가해 주면 해결 될 것으로 판단해서 코드 수정을 해 주시면 될 것 같습니다.

Breakpoint 1, main () at 9012.cpp:8
8	{
(gdb) n
9		int n=0,i,j, check=0, count;
(gdb) n
12	    stack<char> s;
(gdb) n
13	    cin >> count;
(gdb) n
1
15	    for(j=0; j<count; j++)
(gdb) n
17	        check = 0;
(gdb) n
18	        cin >> input;
(gdb) n
(())())
19	        n = strlen(input);
(gdb) n
21	        for(i=0; i<n; i++)
(gdb) disp n
1: n = 7
(gdb) n
23	            if ( input[i] == '(')
1: n = 7
(gdb) n
24	                s.push(input[i]);
1: n = 7
(gdb) n
21	        for(i=0; i<n; i++)
1: n = 7
(gdb) n
23	            if ( input[i] == '(')
1: n = 7
(gdb) disp *input@i
2: *input@i = "("
(gdb) n
24	                s.push(input[i]);
1: n = 7
2: *input@i = "("
(gdb) disp i
3: i = 1
(gdb) n
21	        for(i=0; i<n; i++)
1: n = 7
2: *input@i = "("
3: i = 1
(gdb) n
23	            if ( input[i] == '(')
1: n = 7
2: *input@i = "(("
3: i = 2
(gdb) n
25	            else if(i == 0 && input[i] == ')')
1: n = 7
2: *input@i = "(("
3: i = 2
(gdb) n
30	            else if( i !=0 && input[i]  == ')' )
1: n = 7
2: *input@i = "(("
3: i = 2
(gdb) n
32	                if( s.top() == '(' )
1: n = 7
2: *input@i = "(("
3: i = 2
(gdb) n
33	                    s.pop();
1: n = 7
2: *input@i = "(("
3: i = 2
(gdb) n
21	        for(i=0; i<n; i++)
1: n = 7
2: *input@i = "(("
3: i = 2
(gdb) n
23	            if ( input[i] == '(')
1: n = 7
2: *input@i = "(()"
3: i = 3
(gdb) n
25	            else if(i == 0 && input[i] == ')')
1: n = 7
2: *input@i = "(()"
3: i = 3
(gdb) n
30	            else if( i !=0 && input[i]  == ')' )
1: n = 7
2: *input@i = "(()"
3: i = 3
(gdb) n
32	                if( s.top() == '(' )
1: n = 7
2: *input@i = "(()"
3: i = 3
(gdb) n
33	                    s.pop();
1: n = 7
2: *input@i = "(()"
3: i = 3
(gdb) n
21	        for(i=0; i<n; i++)
1: n = 7
2: *input@i = "(()"
3: i = 3
(gdb) n
23	            if ( input[i] == '(')
1: n = 7
2: *input@i = "(())"
3: i = 4
(gdb) n
24	                s.push(input[i]);
1: n = 7
2: *input@i = "(())"
3: i = 4
(gdb) n
21	        for(i=0; i<n; i++)
1: n = 7
2: *input@i = "(())"
3: i = 4
(gdb) n
23	            if ( input[i] == '(')
1: n = 7
2: *input@i = "(())("
3: i = 5
(gdb) n
25	            else if(i == 0 && input[i] == ')')
1: n = 7
2: *input@i = "(())("
3: i = 5
(gdb) n
30	            else if( i !=0 && input[i]  == ')' )
1: n = 7
2: *input@i = "(())("
3: i = 5
(gdb) n
32	                if( s.top() == '(' )
1: n = 7
2: *input@i = "(())("
3: i = 5
(gdb) n
33	                    s.pop();
1: n = 7
2: *input@i = "(())("
3: i = 5
(gdb) n
21	        for(i=0; i<n; i++)
1: n = 7
2: *input@i = "(())("
3: i = 5
(gdb) n
23	            if ( input[i] == '(')
1: n = 7
2: *input@i = "(())()"
3: i = 6
(gdb) n
25	            else if(i == 0 && input[i] == ')')
1: n = 7
2: *input@i = "(())()"
3: i = 6
(gdb) n
30	            else if( i !=0 && input[i]  == ')' )
1: n = 7
2: *input@i = "(())()"
3: i = 6
(gdb) n
32	                if( s.top() == '(' )
1: n = 7
2: *input@i = "(())()"
3: i = 6
(gdb) n

Program received signal SIGSEGV, Segmentation fault.
main () at 9012.cpp:32
32	                if( s.top() == '(' )
1: n = 7
2: *input@i = "(())()"
3: i = 6
(gdb) 

문제점 수정한 코드는 아래와 같으면 결과가 잘 출력되는 걸 확인 했습니다.

  1 #include <iostream>
  2 #include <stack>
  3 #include <string.h>
  4 
  5 using namespace std;
  6 
  7 int main()
  8 {
  9     int n=0,i,j, check=0, count;
 10     char input[51];
 11 
 12     stack<char> s;
 13     cin >> count;
 14 
 15     for(j=0; j<count; j++){
 16         check = 0;
 17         cin >> input;
 18         n = strlen(input);
 19 
 20         for(i=0; i<n; i++){
 21             if ( input[i] == '(')
 22                 s.push(input[i]);
 23             else if(i == 0 && input[i] == ')'){
 24                 s.push(input[i]);
 25                 break;
 26             }
 27             else if( i !=0 && input[i]  == ')' ){
 28                 if( s.empty() ){
 29                     s.push(input[i]);
 30                 }
 31                 else{
 32                     if( s.top() == '(' )
 33                         s.pop();
 34                     else
 35                         s.push(input[i]);
 36                 }
 37             }
 38         }                          
 39 
 40         if( s.empty() )
 41             cout << "YES" << endl;
 42         else
 43             cout << "NO" << endl;
 44 
 45         while( !s.empty() )
 46             s.pop();
 47     }
 48     return 0;
 49 }                              

#include <iostream>
#include <stack>

using namespace std;

int main()
{
		int count,val,i,total=0;

        stack<int> s;
		//scanf("%d", &count);
        cin >> count;

		while(count>0)
		{
			//scanf("%d", &val);
            cin >> val;

			if( val > 0)
				s.push(val);
			else if (val == 0)
				s.pop();

			count--;
		
		}

		while(!s.empty())
		{
			total += s.top();
            s.pop();
		}

        cout << total << endl;

		return 0;
}