[백준]12789번 도키도키 간식드리미 (스택/ C언어 )

 

 

스택 개념을 활용한 문제

1,2월에 도전했던 문제지만 실패했다. 다시 도전해서 풀게된 문제 중 하나이다. 

스택 개념을 모르고 푼다면 어렵지만 알면 응용해서 꽤 간단하게 구현 가능한 문제이다.

난이도는 백준 기준으로 실버3이다.

https://www.acmicpc.net/problem/12789

12789번: 도키도키 간식드리미

 

 

- 스택(stack)? 

 

스택의 개념을 처음 접하면 나오는 단어인 LIFO(Last-In-First-out) 후입선출 개념이다.

 

스택을 사용하는 예로는 UNDO( 되돌리기 / ctrl + z ), 미로 찾기, 함수 호출, 백 트래킹(undo와 비슷한 개념) 등이 있다.

 

한 공간에 데이터들을 쌓는 push(삽입) 과정을 거쳐 데이터를 다시 반환해야 할 때 쌓여있는 데이터 

 

제일 위에서 부터 pop(삭제)과정을 거친다.  ( 연산을 할 때 삽입 삭제가 가능한지의 여부도 판단하면 좋다. )

 

스택은 top( 젤 위에 있는 데이터 * 사진참조)의 유무에서 모든 연산을 진행한다.

 

원하는 데이터의 공간이 꽉 차서 더 이상 데이터를 삽입 하지 못하는 경우를 오버플로우라고 한다.

 

오버플로우(overflow)의 예는 우리가 c언어로 구현할 때 char의 형태로 129의 값을 반환할 때 다른 값이 나오는 형태를

 

본 적이 있을텐데 이때 그 데이터들이 공간이 부족해서 일어나는 형태를 보여준다.

 

반대로 공간이 텅 빌 때는 언더플로우(underflow)라고 한다.

 

 

- 구글 스택 이미지

- 문제

백준 문제

 

그림을 봤을 때 1열로 서있는 공간에서 번호표 대로 간식을 받아야하고 그 공간 안에서는 번호가 섞여있는 그런 형태이다.

 

 

 

push는 top에 전위식을 사용해서 데이터를 삽입하는 함수를 만든다, 

 

pop은 스택에서 top을 제거하는 과정을 거치는 함수를 만든다.

 

 

#include <stdio.h>

#define max 1001

int stack[max];

int top = EOF;

void push(int data)
{
	stack[++top] = data;
}

int pop()
{
	return stack[top--];
}

int main(void)
{
	int n, num;
	int check = 1;

	scanf("%d", &n);

	while (n != 0)
	{
		scanf("%d", &num);
		if (num == check)
		{
			check++;
			while (stack[top] == check && top >= 0)
			{
				pop();
				check++;
			}
		
		}
		else
		{
			push(num);
		}
		n--;
	}
	if (top == EOF)
	{
		printf("Nice");
	}
	else
	{
		printf("Sad");
	}
	return 0;
}

 

 

- 문제 풀이

 

인원 수를 입력문으로 받고 인원수가 0일 될 때 까지 반복문에서 번호표 배열을 시작한다.

 

while( n != 0 ) >> n--  인원 수를 줄여가며 번호표를 확인한다.

 

num으로 번호표를 받아서 1이면 바로 pop을 하고 번호표의 숫자를 올린다.

 

그러면 구조가 1이 아닌 이상 배열에 쌓이게 된다.

 

그렇게 check++ 을 사용해 번호를 빼주면 되는 형식이다.

 

그래서 push 를 통해 삽입하고 pop을 번호표와 대조하면서 문제를 풀어간다.

 

 

실수 했던 점

 

>> top을 통해 pop을 하는 연산을 할 때 -1이 되기 전까지 설정을 해야하는데 어이 없는 실수로 top != 0 으로 계속 설정하면서 돌렸는데 SAD라는 출력문이 나오길래 고민을 하게 되었고 아직 내가 스택을 이용한 배열 구조의 기본기가 탄탄하지 않음을 느끼게 되는 문제였다. 배열 구조에서는 0부터 시작이기에 스택이 끝나는 EOF를 설정해서 하는게 맞았다. 기본기도 중요하다는 생각을 하게 해준 문제였다고 생각한다.