[백준] - 스택 기본(C++) 10828번 스택 / 28278번 스택2 / 10773번 제로

스택을 기본적인 성질을 이해하고 구현할 수 있다면, 쉽게 해결할 수 있는 백준 문제 3가지를 가져와 보았다.

스택에 대한 설명은 아래 글에서 자세히 적어놓았다.

https://developer-cat.tistory.com/4

[자료구조] - 스택(Stack)의 구조와 구현

 

10828번: 스택

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

10828번: 스택

• push X - 정수 X를 스택에 삽입.
• pop - 스택의 맨 위 데이터를 출력 & 삭제. 만약 스택이 비어있는 경우에는 -1을 출력.
• size - 스택에 들어있는 정수의 개수 출력.
• empty - 스택이 비어있으면 1, 아니면 0 출력.
• top - 스택의 가장 위에 있는 정수 출력. 만약 스택이 빈 경우 -1 출력.

C++ 코드

<알고리즘>

명령 횟수 N을 입력받은 후, for문을 돌면서 N번 반복한다. 명령어가 문자열로 주어지므로 string 변수를 입력받고, 입력받은 string에 따라서 각 명령을 수행한다. push를 입력받았을 경우, 정수를 한 번 더 입력받음으로써 스택에 해당 정수를 삽입한다.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

#define MAX 1000000
int stack[MAX];
int top = -1;

//스택이 비어있는지 검사
int is_Empty(){
	if (top == -1) return 1;
	else return 0;
}

//스택이 가득 차있는지 검사
int is_full() {
	if (top == (MAX-1)) return 1;
	else return 0;
}

//스택에 데이터 삽입
void push(int k) {
	if (is_full() == 1)
		cout << "Overflow";
	else {
		top++;
		stack[top] = k;
	}
}

//스택의 맨 위 데이터 리턴 후 삭제
int pop() {
	if (is_Empty() == 1)
		return -1;
	else {
		int x = stack[top];
		top--;
		return x;
	}
}

//스택의 맨 위 데이터 리턴 (삭제는 하지 않음)
int peek() {
	if (is_Empty() == 1) return -1;
	else return stack[top];
}


//main함수
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;

	int sum = 0;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		int num;

		//push가 입력될 경우 정수를 추가로 입력받기
		if (s == "push") {
			cin >> num;
			push(num);
		}
        
		else if (s == "pop")
			cout << pop() << "\n";
            
		//배열의 인덱스는 0부터 시작하므로 top+1            
		else if (s == "size")
			cout << top + 1 << "\n";
            
		else if (s == "empty")
			cout << is_Empty() << "\n";
            
		else if (s == "top")
			cout << peek() << "\n";
	}
}

 

 

---

28278번: 스택2

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

28278번: 스택 2

앞선 문제와 똑같은 문제이다. 입력을 정수로 받아야 한다는 부분만 다르다. 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

#define MAX 1000000
int stack[MAX];
int top = -1;

int is_Empty(){
	if (top == -1) return 1;
	else return 0;
}

int is_full() {
	if (top == (MAX-1)) return 1;
	else return 0;
}

void push(int k) {
	if (is_full() == 1)
		cout << "Overflow";
	else {
		top++;
		stack[top] = k;
	}
}

int pop() {
	if (is_Empty() == 1) return -1;
	else {
		int x = stack[top];
		top--;
		return x;
	}
}

int peek() {
	if (is_Empty() == 1) return -1;
	else return stack[top];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		if (num == 1) {
			cin >> num;
			push(num);
		}
		else if (num == 2)
			cout << pop() << "\n";
		else if (num == 3)
			cout << top + 1 << "\n";
		else if (num == 4)
			cout << is_Empty() << "\n";
		else if (num == 5)
			cout << peek() << "\n";
	}
}

 

 

---

10773번: 제로

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

10773번: 제로

0을 입력받으면 가장 최근에 쓴 수를 지우고, 아닐 경우 입력받은 수를 쓰는 문제이다.

스택을 이용하여 0이 입력되면 pop연산을 하고, 아니면 push 연산을 하면 해결할 수 있다. 입력이 끝난 후 top 변수를 이용하여 스택에 정수가 남아있는 개수만큼 pop을 하여 스택 내 데이터의 총합을 구하면 된다. 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

#define MAX 1000000
int stack[MAX];
int top = -1;

int is_Empty(){
	if (top == -1) return 1;
	else return 0;
}

int is_full() {
	if (top == (MAX-1)) return 1;
	else return 0;
}

void push(int k) {
	if (is_full() == 1)
		cout << "Overflow";
	else {
		top++;
		stack[top] = k;
	}
}

int pop() {
	if (is_Empty() == 1) return -1;
	else {
		int x = stack[top];
		top--;
		return x;
	}
}

int peek() {
	if (is_Empty() == 1) return -1;
	else return stack[top];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int K;
	cin >> K;

	int sum = 0;
	for (int i = 0; i < K; i++) {
		int num;
		cin >> num;
        	//0이 아닌 수가 들어오면 push
		if (num != 0) {
			push(num);
		}
        	//0 입력 시 최근에 쓴 수 지우기(pop)
		else {
			pop();
		}
	}
    	//스택에 들어있는 데이터 수만큼 pop연산을 하면서 sum에 더하기
	while (top > -1) {
		sum += pop();
	}
	cout << sum;
}