글 읽기 - 반례를 모르겠습니다.. 소스에 대한설명 자세히 썻어요!

porrshe 5년 전 0

일단 게시판글 다읽었어요ㅜㅜ 틀렸다고 나오는데..

질문검색들어가서 넣어볼 수 있는 테케들은 넣어봤는데 잘나와요..ㅜㅜ

스스로 테스트케이스도 만들어 넣어봤는데 잘나와서 도대체 어디서 틀리는지 모르겠습니다..

제 소스는 대략

입력받은 배열방값보다 같거나 작으면 push를 합니다.

2. push나 pop에 관한 연산은 스택을 하나더 만들어서 넣었어요(출력하기 까다로워서 그냥 덱구현했습니다-덱이라고 보시면되용)

3. 1번에서 배열방값하고 i의 값하고 같을테죠 그러면 pop을 시도합니다.

입력받은배열방을 다음방으로 옮겨가면서 그값과 tail->data가 같으면 pop을 계속 실행해주고 다르면 break해서 탈출합니다.

4. 마지막은 result(위의 과정에서 만들어진 수열)와 처음 입력받은 배열을 비교합니다. 다르면 e++시키고 나옵니다.

5. e에 따라 0이면 저장해온 '+', '-'출력, 그게아니면 NO를 출력했습니다.

도와주세여ㅜㅜ

#include <stdio.h>
using namespace std;

typedef struct _node
{
	int data;
	char a;
	_node *before;
	_node *next;
}node;

typedef struct _sta
{
	int size;
	node *head;
	node *tail;
}sta;

sta* create()
{
	sta *s = new sta;
	s->head = NULL;
	s->tail = NULL;
	s->size = 0;
	return s;
}

void push(sta *s, int data,char str)
{
	node *n = new node;
	n->data = data;
	n->before = NULL;
	n->next = NULL;
	n->a = str;
	if (s->size == 0)
	{
		s->head = n;
		s->tail = n;
	}
	else
	{
		n->before = s->tail;
		s->tail->next = n;
		s->tail = n;

	}
	s->size++;
}

void pop(sta *s)
{
	if (s->size == 0)return;
	else if (s->size == 1)
	{
		s->head = NULL;
		s->tail = NULL;
	}
	else
	{
		node *temp = s->tail;
		s->tail = temp->before;
		delete temp;
	}
	s->size--;

}
void popque(sta *s)
{
	if (s->size == 0)return;
	else if (s->size == 1)
	{
		s->head = NULL;
		s->tail = NULL;
	}
	else
	{
		node *temp = s->head;
		s->head = temp->next;
		delete temp;
	}
	s->size--;
}
char arr[100004] = { 0, };
char result[100004] = { 0, };
int main(void)
{
	sta *s = create();
	sta *car = create();
	int a, n,d;
	a = d = 1;
	scanf("%d",&n);
	for (int i = 1; i <= n; i++)scanf("%d", &arr[i]);

	
	for (int i = a; i <= n; i++)
	{
			if (arr[d] >= i)
			{
				push(s, i, 0);
				push(car, i, '+');
			}
			if (arr[d] == i)
			{
				for (int j = d; s->size!=0; j++)
				{
					if (s->tail->data == arr[j])
					{
						result[d] = arr[j];
						pop(s);
						push(car, result[d], '-');
						d++;
					}
					else break;
				}
			}
			a = i + 1;
	}
	int e = 0;
	for (int i = 1; i <= n; i++)
	{
		if (arr[i] != result[i])
		{
			e++;
			break;
		}
	}
	if (e == 0)
	{
		while (car->size != 0)
		{
			printf("%c\n", car->head->a);
			popque(car);
		}
	}
	else printf("NO");
	return 0;
}

djm03178 5년 전 0

arr과 result는 모두 int여야 합니다. char형은 127까지만 저장할 수 있습니다.

porrshe 5년 전 0

제가 정말 왜그랬을까요..허허 넘바보같네요ㅜ감사합니다!

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