[SCTF][C] FILO1 이중스택 구현

교내 해킹대회 SCTF에서 CODING문제로 출제 된 FILO1 문제 write up

언어 & IDE

Lang: C

IDE: DEV C++

 

1. 문제파악

기존 FILO문제에서 스택이 두개가 생기고, 여러 함수가 추가되었다.

2. 구현

1. main

int main(void){
	int* stack1,* stack2;
	int ESP1, ESP2;
	int data;
	int t_case;
	int i, tmp;
	char command[10];
	
	scanf("%d", &t_case);
	stack1 = (int *)calloc(t_case, sizeof(int));
	stack2 = (int *)calloc(t_case, sizeof(int));
	
	for(i=0;i<t_case;i++){
		scanf("%s", command);
		
		if(!strcmp(command,"push")){
			scanf("%d", &data);	
			push(stack1, &ESP1, t_case, data);
			push(stack2, &ESP2, t_case, data);	
		}
		
		else if(!strcmp(command, "pop1")){
				tmp =  pop(stack1, &ESP1);
				if(tmp != 0){
					push(stack2, &ESP2, t_case, tmp);
				}
		}
		else if(!strcmp(command, "pop2")){
				tmp =  pop(stack2, &ESP2);
				if(tmp != 0){
					push(stack1, &ESP1, t_case, tmp);
				}
		}
		
		else if(!strcmp(command, "size1")){
			size(&ESP1);
		}
		else if(!strcmp(command, "size2")){
			size(&ESP2);
		}
		
		else if(!strcmp(command, "empty1")){
			empty(&ESP1);
		}
		else if(!strcmp(command, "empty2")){
			empty(&ESP2);
		}
		
		else if(!strcmp(command, "show")){
			show(stack1, stack2, &ESP1, &ESP2);
		}	
	}
	
	free(stack1);
	free(stack2);
	
	return 0;	
}

기존 FILO문제의 코드를 재활용하다가, 애매해서 처음부터 다시 코딩을 했는데, 시간이 없어 코드가 난잡하다.

먼저 메인함수에는 stack으로 사용할 배열 2개를 동적할당(calloc) 하였다. 

 

특별히 바뀐 점은 malloc이 아닌 calloc을 사용하였다는것 인데 함수 show를 호출하면, 특정상황에서 쓰레기값이 출력되는 경우가 있어, calloc을 사용하여 미리 0으로 초기화를 해두었다. 

 

2. push

void push(int* stack, int* ESP, int stack_size, int data){
	if(stack_size == *ESP){
		puts("overflow");
	}
	else{
		stack[(*ESP)++] = data;
	}
	return ;
}

이 부분은 기존 문제의 함수를 재활용하였다. 

push를 하면 스택1과 스택2에 data를 push한다. 

3. pop

int pop(int* stack, int* ESP){
	int tmp;
	
	if(*ESP == 0){
		puts("-1");
	}
	else{
		tmp = stack[--(*ESP)];
		stack[(*ESP)] = 0;
		return tmp;
	}
	return 0;
}

기존의 함수와 약간의 차이점이 있는데, 문제에서 요구하는 pop은 data를 return하여 다른 스택에 push해줘야한다. 

ps. pop1 & pop2는 코드가 동일하다.

4. size

void size(int* ESP){
	printf("%d\n", *ESP);
	return ;
}

사실 스택에 대해서 조금이라도 이해를 한다면, 이 부분은 설명할 필요는 없을듯하다.

ps. size1 & size2는 코드가 동일하다.

5. empty

void empty(int *ESP){
	
	if(*ESP == 0){
		printf("1\n");
	}
	else{
		printf("0\n");
	}
	return ;
}

pop과 상당히 유사한걸 알 수 있다.

6. show

void show(int* stack1, int* stack2, int* ESP1, int* ESP2){
	int i;
	int max;
	
	if(*ESP1 > *ESP2){
		max = *ESP1;
	}
	else {
		max = *ESP2;
	}
	
	for(i=max-1;i>=0;i--){
		printf("%d %d\n", stack1[i], stack2[i]);
	}
	return ;
}

show도 비슷하다. 

 

3. 테스트

테스트 성공.. ㅎ

4. 전체코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void push(int* stack, int* ESP, int stack_size, int data);
int pop(int* stack, int* ESP);
void size(int* ESP);
void empty(int *ESP);
void show(int* stack1, int* stack2, int* ESP1, int* ESP2);

int main(void){
	int* stack1,* stack2;
	int ESP1, ESP2;
	int data;
	int t_case;
	int i, tmp;
	char command[10];
	
	scanf("%d", &t_case);
	stack1 = (int *)calloc(t_case, sizeof(int));
	stack2 = (int *)calloc(t_case, sizeof(int));
	
	for(i=0;i<t_case;i++){
		scanf("%s", command);
		
		if(!strcmp(command,"push")){
			scanf("%d", &data);	
			push(stack1, &ESP1, t_case, data);
			push(stack2, &ESP2, t_case, data);	
		}
		
		else if(!strcmp(command, "pop1")){
				tmp =  pop(stack1, &ESP1);
				if(tmp != 0){
					push(stack2, &ESP2, t_case, tmp);
				}
		}
		else if(!strcmp(command, "pop2")){
				tmp =  pop(stack2, &ESP2);
				if(tmp != 0){
					push(stack1, &ESP1, t_case, tmp);
				}
		}
		
		else if(!strcmp(command, "size1")){
			size(&ESP1);
		}
		else if(!strcmp(command, "size2")){
			size(&ESP2);
		}
		
		else if(!strcmp(command, "empty1")){
			empty(&ESP1);
		}
		else if(!strcmp(command, "empty2")){
			empty(&ESP2);
		}
		
		else if(!strcmp(command, "show")){
			show(stack1, stack2, &ESP1, &ESP2);
		}	
	}
	
	free(stack1);
	free(stack2);
	
	return 0;	
}

void push(int* stack, int* ESP, int stack_size, int data){
	if(stack_size == *ESP){
		puts("overflow");
	}
	else{
		stack[(*ESP)++] = data;
	}
	return ;
}

int pop(int* stack, int* ESP){
	int tmp;
	
	if(*ESP == 0){
		puts("-1");
	}
	else{
		tmp = stack[--(*ESP)];
		stack[(*ESP)] = 0;
		return tmp;
	}
	return 0;
}

void size(int* ESP){
	printf("%d\n", *ESP);
	return ;
}

void empty(int *ESP){
	
	if(*ESP == 0){
		printf("1\n");
	}
	else{
		printf("0\n");
	}
	return ;
}

void show(int* stack1, int* stack2, int* ESP1, int* ESP2){
	int i;
	int max;
	
	if(*ESP1 > *ESP2){
		max = *ESP1;
	}
	else {
		max = *ESP2;
	}
	
	for(i=max-1;i>=0;i--){
		printf("%d %d\n", stack1[i], stack2[i]);
	}
	return ;
}

ps. top 구현 빼먹었다.. ㅎㅎㅎㅎㅎ