[c언어] 백준 10828번 : 스택 자료구조

Baekjoon 백준, 10828번 자료구조 스택 문제 풀이

 

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

 

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

 

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: deunlee, djm03178

알고리즘 분류

• 자료 구조
• 스택

 

 문제와 확인 예제는 위와 같습니다.

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 10001	// SIZE를 100으로 설정하면 시간초과

int stack[MAX_SIZE];
int count = -1;


//push X: 정수 X를 스택에 넣는 연산이다.
void push(int num) {
	stack[++count] = num;
}

//pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
void pop() {
	if (count != -1) {
		printf("%d\n", stack[count]);
		stack[count--] = 0;
	}
	else
		printf("-1\n");
}

//size: 스택에 들어있는 정수의 개수를 출력한다.
void size() {
	printf("%d\n", count + 1);
}

//empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
void empty() {
	if (count == -1) printf("1\n");
	else printf("0\n");
}

//top: 스택의 가장 위에 있는 정수를 출력. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
void top() {
	if (count != -1) {
		printf("%d\n", stack[count]);
	}
	else printf("-1\n");
}

int main() {
	int n;
	char chosStr[10];

	scanf("%d", &n);	// 반복수

	for (int i = 0; i < n; i++) {
		scanf("%s", &chosStr);
		
		if (strcmp(chosStr, "push") == 0) {
			int num;
			scanf("%d", &num);
			push(num);
		}
		else if (strcmp(chosStr, "pop") == 0) {
			pop();
		}
		else if (strcmp(chosStr, "top") == 0) {
			top();
		}
		else if (strcmp(chosStr, "size") == 0) {
			size();
		}
		else if (strcmp(chosStr, "empty") == 0) {
			empty();
		}
	}
}

 

 시행착오가 몇 번 있었는데, 그 이유가 처음 풀 당시 stack의 배열 크기를 100으로 설정해서 결과는 옳게 나오나 시간초과가 발생했다. 근데, 스택의 사이즈를 100으로 설정한 것이 왜 시간초과의 이유가 되는지 모르겠다.

만약 아시는 분이 계시다면 댓글 부탁드립니다.

 

해당 풀이처럼 코드를 짜면 결과는 아래와 같이 나온다.

 

 

풀이 결과

- 예제 1의 입력 및 출력 결과

 

- 예제 2의 입력 및 출력 결과