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

✅문제

1. n입력

2. 1~n까지 임의의 수열 입력

3. 1~n까지 스택에 pop & push 하면서 저 수열 나오게 함

4. 해당 pop & push 순서를 + 와 - 기호로 표현

 

✅해결 과정

1. 수열 만드는게 불가능한 경우가 어떤 경우일까...?

-> 3 4 5 처럼 연속하는 세 수를 x-1, x, x+1이라 해보자 만약 수열이 x+1(대), x-1(소), x(중) 순서면 불가능함

2. 그럼 일단 저 수열을 배열에 받아서 어떤 세 수를 검사했을 때 첫 수 - 2 = 중간 수, 중간 수 + 1 = 세 번째 수 인지 검사해서 이 경우 ==> NO 출력

3. 그 외: 1~n까지 오름차순으로 스택에 push 하면서 수열값 만나면 pop

 

👊Try 1

/*int형 스택 IntStack(소스)*/
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int max;
  int ptr;
  int *stk;
}IntStack;

/*스택 초기화*/
int Initialize(IntStack *s, int max)
{
  s->ptr = 0;   //일단 스택 비어있어야 메모리 공간 만들 수 있음
  if((s->stk = calloc(max, sizeof(int))) == NULL) //스택구조체s의 스택배열이름 stk에 메모리 공간 할당, 근데 이제 그게 NULL이면 배열 생성에 실패한 거
  {
    s->max = 0; //스택 크기는 0으로 초기화
    return -1;
  }
  //배열 생성 성공하면
  s->max = max; //스택구조체s의 max멤버에게 원하는 스택크기 max 저장
  return 0;
}

/*스택에 데이터 x를 푸시*/
int Push(IntStack *s, int x)
{
  if(s->ptr >= s->max)  //현재 쌓인 데이터 개수가 max 이상이면(가득 찬거)
  {
    return -1;  //push 실패
  }
  //가득 차지 않았다면
  s->stk[s->ptr++] = x; //배열의 ptr위치에 데이터 x 저장
  return 0;
}

/*스택에서 데이터 x를 팝*/
int Pop(IntStack *s, int *x)
{
  if(s->ptr <= 0) //현재 쌓인 데이터 개수(ptr)가 0 이하이면(완전 비어 있는 상태)
  {
    return -1;  //pop 실패
  }
  //비어 있지 않다면
  *x = s->stk[--s->ptr];  //배열의 ptr -1 위치에 있는 데이터를 x에 저장
  return 0;
}

/*스택에서 데이터를 피크(꼭대기 데이터 몰래 엿보기))*/
int Peek(const IntStack *s, int *x)
{
  if(s->ptr <= 0) //비어있으면
  {
    return -1;  //peek 실패
  }
  *x = s->stk[s->ptr-1];
  return 0;
}

/*스택 비우기*/
void Clear(IntStack *s)
{
  s->ptr = 0; //ptr만 0으로 바꿔주면 됨(스택에 쌓인게 없도록)
}

/*스택 용량*/
int Capacity(const IntStack *s)
{
  return s->max;    //스택 최대 용량
}

/*스택에 쌓여 있는 데이터 수*/
int Size(const IntStack *s)
{
  return s->ptr;
}

/*스택이 비었는가?*/
int IsEmpty(const IntStack *s)
{
  return s->ptr <= 0; //비었으면 참(1) return
}

/*스택이 가득 찼는가?*/
int IsFull(const IntStack *s)
{
  return s->ptr >= s->max;    //max이상이면 가득 찬거
}

/*스택에서 검색. 성공 시 인덱스 반환*/
int Search(const IntStack *s, int x)
{
  int i;
  for(i=s->ptr-1; i>=0; i--)
  {
    if(s->stk[i] == x)
    {
      return i; //검색 성공시 그 요소의 인덱스 반환
    }
  }
  return -1;  //검색 실패
}

/*모든 스택 데이터 출력*/
void Print(const IntStack *s)
{
  int i;
  for(i=0; i<s->ptr; i++)
  {
    printf("%d ", s->stk[i]);
  }
  putchar('\n');
}

/*스택 종료*/
void Terminate(IntStack *s)
{
  if(s->stk != NULL)  //스택이 존재한다면
  {
    free(s->stk); //스택배열 메모리 해제
  }
  s->max = s->ptr = 0;  //max와 ptr값을 0으로 초기화
}

int main()
{
  IntStack s; //스택 구조체 s
  int n, i, j=0;
  int *array; //수열 배열
  int peek, pop, push;
  int count = 0;  //pop한 횟수

  scanf("%d", &n);
  array = calloc(n, sizeof(int));

  //수열 입력받기
  for(i=0; i<n; i++)
  {
    scanf("%d", &array[i]);
  }

  //크기 n인 스택 생성
  if(Initialize(&s, n) == -1)  //(스택 max값 n)
  {
    puts("스택 생성에 실패하였습니다.\n");
    return 1; //프로그램 끝내기
  }
  
  //수열 만드는거 불가능한 경우
  for(i=0; i<n-2; i++)
  {
    if(array[i]-2 == array[i+1] && array[i+1] + 1 == array[i+2])
    {
      printf("NO\n");
      return 0;
    }
  }

  push = 1;
  j=0;
  Push(&s, push);
  Peek(&s, &peek);
  while(push <= n)
  {
    if(peek != array[j]){
     Push(&s, ++push);
     printf("+\n");
    }
    else{
      Pop(&s, &pop);
      printf("-\n");
      j++;
    }
  }

  Terminate(&s);  //스택 해제
  return 0;
}

 

❓문제 찾는 중