[C] 백준 | 1874번 코드 - 스택 수열

>문제

> 핵심

스택

>풀이과정

문제가 뭔소린가.. 싶어서 문제를 이해하는데 조금 시간이 걸렸다.

그래도 이해하고 난 후 코드를 짜는건 크게 어렵지 않았다.

 

num=1부터 오름차순으로만 증가!. (e : 입력값)

1. 스택의 Top < e : e에 도달하기 전까지 push, num++

2. 스택의 Top > e : e에 도달하기 전까지 pop,  num은 고정.

3. 스택의 Top != e : 수열을 만들 수 없음. chk = 0 으로 체크 후 break.

4. 스택의 Top == e : 해당 값을 pop 하고 위 과정 반복.

 

하나 고려해야 할 점은 정수를 입력받고 나서 바로 + 혹은 - 를 찍으면 안되고,

모든 정수를 입력받은 후에 만들수 있는 수열인지, 아닌지 체크를 한 다음 정답을 출력해야하므로 따로 정답배열을 만들어줘야 한다.

 

answer 배열은 그리고 최소 n의 두배가 필요하다.

사실 왜 두배인지 정확히는 모르겠다. 질문게시판에 보니까 그렇게 써있더라.

그래도 대충 1, 5만, 2, 10만 이렇게 입력했다고 가정하면, +, - 개수가 얼핏봐도 10만개는 훌쩍 뛰어넘어버린다는건 알 수 있다.

2 1 2 를 입력해보면 + - + -, 4개가 출력되므로 적어도 answer[SIZE * 2] 크기가 필요함

 

그리고 그렇게 되면 배열의 크기가 20만이 넘어가니까 전역변수 혹은 동적할당으로 선언해주는것 잊지말자!

 

 

아니면 스택 쌓기를 두번해도 된다.. 처음엔 나도 그렇게 풀었따

첫 스택쌓기는 +, - 출력 없이 수열 생성 가능 여부만 체크, 두번째 스택쌓기는 +, - 출력해주기 하는 방식으로..

근데 시간이 두배로 들어가니까 쫌 비효율적이다. 

 

>깨달은점

무작정 코딩하면서 때려맞추기 식으로 풀기보다는 먼저 계획을 세워놓고 코딩해보는 습관을 들이자

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define SIZE 100000

char answer[SIZE * 2];

typedef struct
{
	int stack[SIZE];
	int n;
}StackType;

void init_stack(StackType* s)
{
	s->n = -1;
}

int is_empty(StackType* s)
{
	return (s->n == -1);
}

int is_full(StackType* s)
{
	return (s->n == SIZE - 1);
}

void push(StackType* s, int e)
{
	if (is_full(s))
		return;

	s->stack[++s->n] = e;
}

int pop(StackType* s)
{
	if (is_empty(s))
		return -1;

	int tmp = s->stack[s->n--];
	return tmp;
}

int top(StackType* s)
{
	if (is_empty(s)) /*스택이 비어있으면 -1 리턴*/
		return -1;
	else
		return s->stack[s->n];
}

int main()
{
	StackType s;
	init_stack(&s);

	int i, n, e, num = 1, chk = 1, idx = 0;

	scanf("%d", &n);

	for (i = 0; i < n; i++) /*수열이 가능한지 체크*/
	{
		scanf(" %d", &e);

		if (top(&s) < e)
		{
			while (top(&s) < e)
			{
				push(&s, num++);
				answer[idx++] = '+';
			}
		}
		else if (top(&s) > e)
		{
			while (top(&s) > e)
			{
				pop(&s);
				answer[idx++] = '-';
			}
		}

		if (top(&s) != e)
		{
			chk = 0;
			break;
		}
		else
		{
			pop(&s);
			answer[idx++] = '-';
		}
	}

	if (chk == 0) /*불가능한 수열이면 정답을 출력하지 않음*/
	{
		printf("NO\n");
	}
	else
	{
		for (i = 0; i < idx; i++)
		{
			printf("%c\n", answer[i]);
		}
	}

	return 0;
}