백준 1874번 : 스택 수열 [C언어]

문제출처

www.acmicpc.net/problem/1874 

1874번: 스택 수열

자료구조 복습을 위한 관련 문제들을 풀 것이다.

 

스택에 관련된 문제인데 처음에 문제가 조금 이해가 안 됐다.

정리를 조금 하자면

 

처음에 입력된 숫자 n은 몇개의 숫자가 입력될지를 나타내는 값이고,

 

두번째 줄 부터 입력되는 숫자들 전체가 하나의 수열이다.(개인적으로 일정한 규칙을 가지는게 수열아닌가? 라는 때문에 조금 애를 먹었다. 찾아보니 수열은 그냥 수를 나열한 것에 순번을 붙이는 것이지만 교육과정에선 규칙을 가지는게 수열이라고 가르친다고 한다.)

 

즉 [4,3,6,8,7,5,1]이 하나의 수열인것. 1부터 8까지 차례로 오름차순으로 스택에 넣으면서 입력된 것과 같은 수열을 만들 수 있는지 없는지 판단하는 프로그램을 짜면된다.

 

처음에 진행한 코드인데 런타임에러가 떴다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#define MAX_STACK_SIZE 100
typedef int element;
typedef struct {
    element data[MAX_STACK_SIZE];
    int top;
}StackType;

void init_stack(StackType* s)
{
    s->top = -1;
}
// 공백 상태 검출 함수
int is_empty(StackType* s)
{
    return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType* s)
{
    return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType* s, element item)
{
    if (is_full(s)) {
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType* s)
{
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[(s->top)--];
}
// 피크함수
element peek(StackType* s)
{
    if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->data[s->top];
}
int check_seq(const int* seq[], int n)
{
    StackType s;
    char ans[100000];
    int index = 0, j = 0;

    init_stack(&s);

    for (int i = 1; i <= n; i++) {
        push(&s, i);
        ans[index++] = '+';
        while (peek(&s) == seq[j]) {
            pop(&s);
            ans[index++] = '-';
            j++;
            if (is_empty(&s)) break;
        }
    }

    ans[index] = '\n';

    if (is_empty(&s)) {
        for (int i = 0; ans[i] != '\n'; i++) {
            printf("%c\n", ans[i]);
        }
    }
    else return 0;
}
int main()
{
    int n;
    int seq[100000];

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &seq[i]);
    }

    if (check_seq(seq, n) == 0)
        printf("NO\n");
}

 

스택에 대한 설명은 따로 적지 않겠다.

 

입력받은 숫자를 배열로 만들고

정답(+,-)을 출력할 배열을 따로 하나 만들었다.

1부터 오름차순으로 스택에 집어넣고 ans에 +추가

push를 하다가 배열의 첫번째 숫자를 만나게되면 pop을 한뒤 수열의 인덱스도 하나 증가시킨다.

이 과정을 반복하면 수열을 만들 수 있다면 스택은 비게된다.

스택이 만약 비어있지 않다면 배열을 만들 수 없는 것이므로 0을 반환한다.

 

런타임 에러가 난 이유는 내가 처음에 define한 스택의 max가 100으로 설정되어 있어서고, ans의 크기를 10만으로 잡았기 때문.

ans는 n의 최대크기의 2배여야 한다. push pop이 반복되어야 하므로.

 

고쳤는데 이번엔 그냥 틀렸다.

디버깅 해보니 스택오버 플로우라고 나오며 그냥 아예 실행이 되지 않았다.

이유를 도저히 모르겠어서 일단 check_seq라는 함수를 삭제하고 해당내용을 메인함수로 옮겼더니 풀렸다.

아래 코드가 맞은 코드다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#define MAX_STACK_SIZE 100000
typedef int element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
}StackType;
void init_stack(StackType* s)
{
	s->top = -1;
}
// 공백 상태 검출 함수
int is_empty(StackType* s)
{
	return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType* s)
{
	return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType* s, element item)
{
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType* s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[(s->top)--];
}
// 피크함수
element peek(StackType* s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[s->top];
}
int main()
{
	int n;
	int seq[100000];//배열
	StackType s;
	char ans[200001]; //+ or - 가 입력될 배열
	int aIdx = 0, sIdx = 0;
	
	init_stack(&s);

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &seq[i]);
	}

	for (int i = 1; i <= n; i++) {
		push(&s, i); //수를 오름차순으로 push함
		ans[aIdx++] = '+'; //push했으므로 +추가
		while (peek(&s) == seq[sIdx]) { //스택에 들어있는 값이 수열과 같다면
			pop(&s);
			ans[aIdx++] = '-';//pop했으므로 -추가
			sIdx++; //수열의 다음 수를 보기 위한 인덱스증가
			if (is_empty(&s)) break;//스택이 비어있다면 while문을 빠져나와야 top -1의 상태에 접근하지 않게됨
		}
	}
	ans[aIdx] = '\n';
	if (is_empty(&s)) { //스택이 비어있지 않다면 수열이 완성되지 않음
		for (int i = 0; ans[i] != '\n'; i++) {
			printf("%c\n", ans[i]);
		}
	}
	else
		printf("NO\n");
}

 

처음 함수가 틀린이유에 대해서 적어보려고 한다.

날림으로 대충 공부하면 이렇게 된다를 보여주는 좋은 예시 같은데

바로 내가 실수한부분 int check_seq(const int* seq[], int n)

여기다 *이걸 붙인거!!! 대체 내가 왜 붙였는지 아직도 내 스스로를 이해 못하겠다.

왜 포인터로 생각했을까 그러니까 자꾸 에러가 뜨지ㅠㅠ

참고로 저걸 지우니 바로 돌아가고 맞았다.

다음부턴 꼼꼼히 살펴볼것...

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#define MAX_STACK_SIZE 100000
typedef int element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
}StackType;
void init_stack(StackType* s)
{
	s->top = -1;
}
// 공백 상태 검출 함수
int is_empty(StackType* s)
{
	return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType* s)
{
	return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType* s, element item)
{
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType* s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[(s->top)--];
}
// 피크함수
element peek(StackType* s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return s->data[s->top];
}
int check_seq(const int seq[], int n)
{
	StackType s;
	char ans[200001];
	int index = 0, j = 0;

	init_stack(&s);

	for (int i = 1; i <= n; i++) {
		push(&s, i);
		ans[index++] = '+';
		while (peek(&s) == seq[j]) {
			pop(&s);
			ans[index++] = '-';
			j++;
			if (is_empty(&s)) break;
		}
	}

	ans[index] = '\n';

	if (is_empty(&s)) {
		for (int i = 0; ans[i] != '\n'; i++) {
			printf("%c\n", ans[i]);
		}
	}
	else return 0;

}
int main()
{
	int n;
	int seq[100000];

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &seq[i]);
	}

	if (check_seq(seq, n) == 0)
		printf("NO\n");
}