글 읽기 - 반례 좀 찾아주실 수 있나요..??

sks1cjswo 4년 전 0

제 나름대로 테스트 해봤을 때는 문제 없는거 같은데 틀렸습니다 나오네요 ㅠㅠ

#include <stdio.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define UNSTARTED -1
typedef char Data;

typedef struct stack
{
	Data arr[200000];
	int top;
}stack;

void init(stack *ps)
{
	ps->top = -1;
}

int empty(stack * ps)
{
	if (ps->top == -1)return TRUE;
	else return FALSE;
}

void push(stack *ps, Data data)
{
	ps->top += 1;
	ps->arr[ps->top] = data;
}

Data pop(stack *ps)
{
	Data rdata = ps->arr[ps->top];
	ps->top -= 1;
	return rdata;
}

Data peek(stack*ps)
{
	return ps->arr[ps->top];
}

int main()
{

	stack rs, ls;
	init(&rs); init(&ls);
	//괄호문자열 입력
	Data input[100];
	scanf("%s", input);

	//입력 문자열 왼쪽 스택에 모두 push
	int len = strlen(input);
	for (int k = 0; k < len; k++)push(&rs, input[k]);
	int stick = 0;
	int frag = 0;
	int num = 0;
	int state = UNSTARTED;
	for (int k = 0; k < len; k++)
	{
		Data tmp = pop(&rs);
		if (tmp == ')')
		{
			num++;
			state = TRUE;
			if (peek(&rs) != '('&&!empty(&rs)) stick++;
		}
		if (tmp == '(')
		{
			num--;
			if (num < 0)break;
			if (state == UNSTARTED)break;
			if (state == TRUE)
			{
				frag += stick;
				state = FALSE;
			}
			else
			{
				frag++;
				stick--;
			}
		}
	}
	printf("%d", frag);
	printf("\n");
}

sks1cjswo 4년 전 0

아래와 같이 수정해서 해결하였습니다.

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

#define ARRNUM 100000
#define TRUE 1
#define FALSE 0

typedef struct stack
{
	char arr[ARRNUM];
	int top;
}stack;

int empty(stack *stack)
{
	if (stack->top == -1)
		return TRUE;
	else 
		return FALSE;
}

void init(stack *stack)
{
	stack->top = -1;
}

void push(stack *stack,char data)
{
	stack->top += 1;
	stack->arr[stack->top] = data;
}

char pop(stack *stack)
{
	if (stack->top == -1)
	{
		printf("stack memory error");
		return FALSE;
	}
	char rdata = stack->arr[stack->top];
	stack->top -= 1;
	return rdata;
}

char peek(stack *stack)
{
	if (stack->top == -1)
	{
		printf("stack memory error");
		return FALSE;
	}
	return stack->arr[stack->top];
}

int main()
{
	int stick = 0;
	int frag = 0;
	stack s;
	init(&s);
	char input[ARRNUM] = { 0 };
	scanf("%s", input);
	int len = strlen(input);
	for (int i = 0; i < len; i++)push(&s, input[i]);

	while (!empty(&s))
	{
		char popdata = pop(&s);
		switch (popdata)
		{
		case ')':
		{
			if (peek(&s) == ')')stick++;
			else//raser일 때
			{
				pop(&s);
				frag += stick;
			}
			break;
		}
		case '(':
		{
			stick--;
			frag++;
			break;
		}
		}
	}
	printf("%d", frag);
}

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

문제

문제

출처

ICPC

반례 좀 찾아주실 수 있나요..??

sks1cjswo 4년 전 0

sks1cjswo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말