ITwork

https://www.acmicpc.net/problem/10026 

[풀이과정]

1.R,G,B 각 글자에 대해서 FloodFill을 이용해서 글자가 상하좌우에 연결된 부분을 찾는다.

2.전체 맵을 각 글자의 묶음들이 있는 걸 count해서 R,G,B 각 글자에 대해서 숫자를 count한다.

3.적록 색맹을 경우는 R를 G로 변경하는 작업을 해 준다.

4.1번 부터 동일한 과정으로 R,G에 대한 count를 해주면 된다.

/*백준 10026 적록색약*/
#include<iostream>
#include<memory.h>
using namespace std;
#define MAXN (int)1e2+10
char map[MAXN][MAXN];
int visited[MAXN][MAXN];//방문 표시
int N;//행,열 
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};
bool isInside(int a, int b){
	return ( (a>=0) && (a<N) && (b>=0) && (b<N));
}
bool DFS(int y, int x, char c){	
	
	if(isInside(y,x) && visited[y][x]==0 && map[y][x]==c){
		visited[y][x]=1;
		for(int i=0; i<4; i++){
			DFS(y+dy[i],x+dx[i],c);
			//cout<<y+dy[i]<<' '<<x+dx[i]<<endl;
		}	
		return true;
	}else{
		return false;
	}
}
int Calc(int c){
	int cnt=0;
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			if(map[i][j]==c)
				cnt+=DFS(i,j,c);
		}
	}
	return cnt;
}
void remap(){
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			if(map[i][j]=='R')
				map[i][j]='G';
		}
	}
}
void Solve(){
	int cnt1=0,cnt2=0;
	cnt1+=Calc('R');
	cnt1+=Calc('G');
	cnt1+=Calc('B');
	memset(visited,false,sizeof(visited));
	remap();
	cnt2+=Calc('G');
	cnt2+=Calc('B');
	cout<<cnt1<<' '<<cnt2<<endl;
}
void InputData(){
	cin>>N;
	for(int i=0; i<N; i++){
			cin>>map[i];
	}
}
int main(){
	InputData();
	Solve();
	return 0;
}

www.acmicpc.net/problem/2751

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

2750문제에서 array size만 1000000로 변경하였다. 

/*baekjoon 2751 수 정렬하기2 */
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX 1000001

int main()
{
	int data[MAX];
	int i,j, N;
	int tmp, exchg;

	vector<int> v;

	//input data size
	cin >> N;

	//input data
	for(i=0; i<N; i++) {
		cin >> data[i];
		v.push_back(data[i]);
	}

	sort(v.begin(), v.end());
	for(vector<int>::iterator it=v.begin(); it<v.end(); it++)
		printf("%d\n", *it );
		
	return 0;
}
/*baekjoon 2751 수 정렬하기2 */

www.acmicpc.net/problem/2164

N=4일 경우 

1 2 3 4

규칙 : 아래 반복 

맨 위 카드 버림 --> 맨 위 카드를 맨 아래로 이동 --> 맨 위카드 버림 --> 맨 위카드를 맨 아래로 이동 

1 2 3 4

맨 위 카드 버림

2 3 4

맨 위 카드 맨 아래 

3 4 2

맨 위 카드 버림

4 2

맨 위 카드 맨 아래로

2 4

맨 위 카드 버림

4

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
#define MAX_N 100
queue<int> q;


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


	int i,n,tmp;
	cin >> n;



	for(i =1; i <= n; i++ ){
		q.push(i);
	}

	while( 1 ){
		if( q.size() ==1)
			break;

		q.pop();
		tmp = q.front();	
		q.pop();
		q.push(tmp);
	}

	cout << q.front();
		
	return 0;
}

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 }