글 읽기 - 출력초과에 대한 조언 부탁드립니다.

gbkim542 6년 전 0

출력초과가 나오는데 예외를 찾지 못하겠습니다.

여러번 시도하였지만 모든 결과가 잘 나오고, 코드상의 오류도 찾지 못하였습니다.

조언 해주시면 감사하겠습니다.

#pragma warning(disable: 4996)

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

//스택 관련 구조체, 함수 
typedef char Data;

typedef struct _node
{
	Data data;
	struct _node * next;
} Node;

typedef struct _listStack
{
	Node * head;
} ListStack;

typedef ListStack Stack;

void StackInit(Stack * pstack)
{
	pstack->head = NULL;
}

int SIsEmpty(Stack * pstack)
{
	if (pstack->head == NULL)
		return 1;
	else
		return 0;
}

//데이터 삽입
void SPush(Stack * pstack, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));

	newNode->data = data;
	newNode->next = pstack->head;

	pstack->head = newNode;
}

//마지막에 들어간 데이터 반환 후 삭제
Data SPop(Stack * pstack)
{
	Data rdata;
	Node * rnode;

	rdata = pstack->head->data;
	rnode = pstack->head;

	pstack->head = pstack->head->next;
	free(rnode);

	return rdata;
}

//마지막에 들어간 데이터 반환, 삭제x
Data SPeek(Stack * pstack)
{
	return pstack->head->data;
}

int main(void)
{
	int I, J = 0;
	int fidx, bidx;
	int s_length, w_length;
	int del;
	int state = 0;
	int ExistWordFlag = 1; //string 내에 단어 존재하면 1
	int CNT = 0;           //단어를 검열한 회수
	char Word[25];
	char String[300000];

	Stack f_stack;
	Stack b_stack;
	StackInit(&f_stack);
	StackInit(&b_stack);

	scanf("%s", &Word);
	scanf("%s", &String);

	s_length = strlen(String);
	w_length = strlen(Word);
	fidx = 0;
	bidx= s_length - 1;

	while (ExistWordFlag) 
	{
		for (I = fidx; I <= bidx; I++)
		{
			SPush(&f_stack, String[I]);

			if (J != w_length)
			{
				if (Word[J] == SPeek(&f_stack))//단어와 stack에 저장된 문자가 일치하는지
				{
					J++;
					if (J == w_length) //마지막 문자가 일치하는 경우
					{
						ExistWordFlag = 1;
						for (del = 0; del < w_length; del++)
							SPop(&f_stack);
						fidx = I+1;
						J = w_length - 1;
						break;
					}
					else if (I == bidx)//문자가 일치하지만 string의 맨 마지막 글자 일 때
					{
						ExistWordFlag = 0;
						continue;
					}
				}
				else
				{
					if (!J||I==bidx) //첫번째 문자부터 일치하지 않으면 or string의 마지막 글자
					{
						ExistWordFlag = 0;
						continue;
					}
					else  //두번째 이상인 문자부터 일치하지 않으면 
					{
						for (del = 0; del < J; del++) //두번째 문자부터는 stack에서 삭제
						{
							SPop(&f_stack);
						}
						I -= J;
						J = 0;
					}
				}
			}
		}

		if (!ExistWordFlag||(bidx<fidx))
			break;

		for (I = bidx; I >= fidx; I--)
		{
			SPush(&b_stack, String[I]);

			if (J != -1)
			{
				if (Word[J] == SPeek(&b_stack))
				{
					J--;
					if (J == -1)
					{
						ExistWordFlag = 1;
						for (del = 0; del < w_length; del++)
							SPop(&b_stack);
						bidx = I-1;
						J = 0;
						break;
					}
					else if(I == fidx)
					{
						ExistWordFlag = 0;
						continue;
					}
				}
				else
				{
					if (J == w_length - 1||I==fidx) //첫번째 문자부터 일치하지 않으면
					{
						ExistWordFlag = 0;
						continue;
					}
					else  //두번째 이상인 문자부터 일치하지 않으면 
					{
						for (del = 0; del < w_length - 1 - J; del++) //두번째 문자부터는 stack에서 삭제
						{
							SPop(&b_stack);
						}
						I -= w_length - 1 - J;
						J = w_length - 1;
					}
				}
			}
		}
		
	}
	
	//f_stack은 뒤집어서 출력
	while (!SIsEmpty(&f_stack))
	{
		String[CNT++]=SPop(&f_stack);
	}
	for (I = CNT-1; I >= 0; I--) 
	{
		printf("%c", String[I]);
	}
	//b_stack 그대로 출력
	while (!SIsEmpty(&b_stack))
	{
		printf("%c", SPop(&b_stack));
	}
	
	return 0;
}

kimsy96 6년 전 1

abba

ababbaba

요거이상하지않나요

gbkim542 6년 전 0

위 예로 실행해보니 abba 가 출력되는데 제대로 출력되는 것 아닌가요..?

kimsy96 6년 전 1

없어져야하는거아닌가요

안쪽 abba 없애고

남은 abba없애서

kimsy96 6년 전 1

처음으로 등장하는 abba를 없애면 마지막으로 등장하는 abba가또 생기니 그걸없애야하는거같습니다.

아직안풀어봐서 대충 훑어보고 답변드린건데,

방금 통과받은 분 소스로 확인해보니

없어지는게맞는거같습니다

gbkim542 6년 전 0

내 말씀하신 부분이 문제가 있었습니다.

그런데 그부분을 수정하니 출력초과는 해결되었지만 틀렸다고 나오네요..

#pragma warning(disable: 4996)

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

//스택 관련 구조체, 함수 
typedef char Data;

typedef struct _node
{
	Data data;
	struct _node * next;
} Node;

typedef struct _listStack
{
	Node * head;
} ListStack;

typedef ListStack Stack;

void StackInit(Stack * pstack)
{
	pstack->head = NULL;
}

int SIsEmpty(Stack * pstack)
{
	if (pstack->head == NULL)
		return 1;
	else
		return 0;
}

//데이터 삽입
void SPush(Stack * pstack, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));

	newNode->data = data;
	newNode->next = pstack->head;

	pstack->head = newNode;
}

//마지막에 들어간 데이터 반환 후 삭제
Data SPop(Stack * pstack)
{
	Data rdata;
	Node * rnode;

	rdata = pstack->head->data;
	rnode = pstack->head;

	pstack->head = pstack->head->next;
	free(rnode);

	return rdata;
}

//마지막에 들어간 데이터 반환, 삭제x
Data SPeek(Stack * pstack)
{
	return pstack->head->data;
}

int main(void)
{
	int I, J = 0;
	int fidx, bidx;
	int s_length, w_length;
	int del;
	int ExistWordFlag = 1; //string 내에 단어 존재하면 1
	int CNT = 0;           //단어를 검열한 회수
	char Word[26];
	char String[300001];
	char TString[300001];

	Stack f_stack;
	Stack b_stack;
	StackInit(&f_stack);
	StackInit(&b_stack);

	scanf("%s", &Word);
	scanf("%s", &String);

	s_length = strlen(String);
	w_length = strlen(Word);
	fidx = 0;
	bidx= s_length - 1;

	while (1) 
	{
		while (1)
		{
			for (I = fidx; I <= bidx; I++)
			{
				SPush(&f_stack, String[I]);

				if (J != w_length)
				{
					if (Word[J] == SPeek(&f_stack))//단어와 stack에 저장된 문자가 일치하는지
					{
						J++;
						if (J == w_length) //마지막 문자가 일치하는 경우
						{
							ExistWordFlag = 1;
							for (del = 0; del < w_length; del++)
								SPop(&f_stack);
							fidx = I + 1;
							J = w_length - 1;
							break;
						}
						else if (I == bidx)//문자가 일치하지만 string의 맨 마지막 글자 일 때
						{
							ExistWordFlag = 0;
							continue;
						}
					}
					else
					{
						if (!J || I == bidx) //첫번째 문자부터 일치하지 않으면 or string의 마지막 글자
						{
							ExistWordFlag = 0;
							continue;
						}
						else  //두번째 이상인 문자부터 일치하지 않으면 
						{
							for (del = 0; del < J; del++) //두번째 문자부터는 stack에서 삭제
							{
								SPop(&f_stack);
							}
							I -= J;
							J = 0;
						}
					}
				}
			}

			if (!ExistWordFlag || (bidx < fidx))
			{
				break;
			}

			for (I = bidx; I >= fidx; I--)
			{
				SPush(&b_stack, String[I]);

				if (J != -1)
				{
					if (Word[J] == SPeek(&b_stack))
					{
						J--;
						if (J == -1)
						{
							ExistWordFlag = 1;
							for (del = 0; del < w_length; del++)
								SPop(&b_stack);
							bidx = I - 1;
							J = 0;
							break;
						}
						else if (I == fidx)
						{
							ExistWordFlag = 0;
							continue;
						}
					}
					else
					{
						if (J == (w_length - 1) || I == fidx) //첫번째 문자부터 일치하지 않으면
						{
							ExistWordFlag = 0;
							continue;
						}
						else  //두번째 이상인 문자부터 일치하지 않으면 
						{
							for (del = 0; del < (w_length - 1 - J); del++) //두번째 문자부터는 stack에서 삭제
							{
								SPop(&b_stack);
							}
							I += (w_length - 1 - J);
							J = w_length - 1;
						}
					}
				}
			}
			if (!ExistWordFlag || (bidx < fidx))
			{
				break;
			}
		}

		if (fidx == 0)
			break;

		CNT = 0;
		
		//f_stack은 뒤집어서 출력
		while (!SIsEmpty(&f_stack))
		{
			TString[CNT++] = SPop(&f_stack);
		}
		for (I = CNT - 1; I >= 0; I--)
		{
			String[CNT-1-I] = TString[I];
		}
		//b_stack 그대로 출력
		while (!SIsEmpty(&b_stack))
		{
			String[CNT++] = SPop(&b_stack);
		}

		ExistWordFlag = 1;
		J = 0;
		fidx = 0;
		bidx = CNT - 1;
	}
	
	printf("%.*s", CNT, String);
	
	
	return 0;
}

kimsy96 6년 전 1

CHCI 문제는 공식사이트에서 테스트케이스를 제공하니

한번확인해보세요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

출력초과에 대한 조언 부탁드립니다.

gbkim542 6년 전 0

kimsy96 6년 전 1

gbkim542 6년 전 0

kimsy96 6년 전 1

kimsy96 6년 전 1

gbkim542 6년 전 0

kimsy96 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말