congcoding

1. 문제 링크

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

2. 문제 설명

스택 수열을 입력받은 후 push와 pop으로 해당 수열을 만들 수 있는 경우 push는 +, pop은 -로 표현하고,

불가능한 경우 NO를 출력하는 문제입니다.

3. 소스코드

BOJ 1874번 스택 수열 C++ 풀이입니다.

#include <iostream>
#include <stack>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, num, cnt = 1;
	stack<int> s;
	string result = "";
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> num;
		if (num >= cnt) {
			while (num + 1 != cnt) {
				s.push(cnt++);
				result += "+\n";
			}
			s.pop();
			result += "-\n";
		}
		else {
			if (s.top() == num) {
				s.pop();
				result += "-\n";
			}
			else {
				result = "NO";
				break;
			}
		}
	}
	cout << result;

	return 0;
}

먼저 스택에 넣을 수 cnt를 1로 초기화합니다.

17번 라인 if문을 통해 입력받은 수 num이 cnt와 같거나 크면

cnt가 num과 같아질 때 까지 스택에 cnt를 push하고 result에 +를 이어 붙입니다.

그리고 해당 수를 출력하기 위해 pop을 하고 result에 -를 이어 붙입니다.

예를 들어 처음에 4를 입력받으면 스택에 1, 2, 3, 4를 push하므로 +를 4번 출력하고, 4를 pop하고 -를 1번 출력합니다.

25번 라인 else문을 통해 입력받은 수 num이 cnt보다 작으면

스택의 top이 num과 같은지 확인하고, 같으면 해당 수를 출력하기 위해 pop을 하고 result에 -를 이어 붙입니다.

스택의 top이 num과 같지 않으면 주어진 스택 수열을 만들 수 없으므로 result에 NO를 저장하고 for문을 탈출합니다.

최종적으로 result를 출력하면 됩니다. 

1. 문제 링크

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

2. 문제 설명

덱을 구현하는 문제입니다.

3. 소스코드

BOJ 10866번 덱 C++ 풀이입니다.

#include <iostream>
#include <deque>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, X;
	deque<int> D;
	string op;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> op;
		if (op == "push_front") {
			cin >> X;
			D.push_front(X);
		}
		else if (op == "push_back") {
			cin >> X;
			D.push_back(X);
		}
		else if (op == "pop_front") {
			if (D.empty()) cout << -1 << '\n';
			else {
				cout << D.front() << '\n';
				D.pop_front();
			}
		}
		else if (op == "pop_back") {
			if (D.empty()) cout << -1 << '\n';
			else {
				cout << D.back() << '\n';
				D.pop_back();
			}
		}
		else if (op == "size") {
			cout << D.size() << '\n';
		}
		else if (op == "empty") {
			cout << D.empty() << '\n';
		}
		else if (op == "front") {
			if (D.empty()) cout << -1 << '\n';
			else cout << D.front() << '\n';
		}
		else if (op == "back") {
			if (D.empty()) cout << -1 << '\n';
			else cout << D.back() << '\n';
		}
	}

	return 0;
}

STL에 있는 deque을 이용해서 풀었습니다.

pop_front, pop_back, front, back함수를 호출할 때 덱이 비어있으면 에러가 발생하므로,

empty함수로 덱이 비어있는지 먼저 확인한 후 사용해야 합니다.

1. 문제 링크

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

2. 문제 설명

큐를 구현하는 문제입니다.

3. 소스코드

BOJ 10845번 큐 C++ 풀이입니다.

#include <iostream>
#include <queue>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, X;
	queue<int> Q;
	string op;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> op;
		if (op == "push") {
			cin >> X;
			Q.push(X);
		}
		else if (op == "pop") {
			if (Q.empty()) cout << -1 << '\n';
			else {
				cout << Q.front() << '\n';
				Q.pop();
			}
		}
		else if (op == "size") {
			cout << Q.size() << '\n';
		}
		else if (op == "empty") {
			cout << Q.empty() << '\n';
		}
		else if (op == "front") {
			if (Q.empty()) cout << -1 << '\n';
			else cout << Q.front() << '\n';
		}
		else if (op == "back") {
			if (Q.empty()) cout << -1 << '\n';
			else cout << Q.back() << '\n';
		}
	}

	return 0;
}

STL에 있는 queue를 이용해서 풀었습니다.

pop, front, back함수를 호출할 때 큐가 비어있으면 에러가 발생하므로,

empty함수로 큐가 비어있는지 먼저 확인한 후 사용해야 합니다.

1. 문제 링크

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

2. 문제 설명

스택을 구현하는 문제입니다.

3. 소스코드

BOJ 10828번 스택 C++ 풀이입니다.

#include <iostream>
#include <stack>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, X;
	stack<int> S;
	string op;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> op;
		if (op == "push") {
			cin >> X;
			S.push(X);
		}
		else if (op == "pop") {
			if (S.empty()) cout << -1 << '\n';
			else {
				cout << S.top() << '\n';
				S.pop();
			}
		}
		else if (op == "size") {
			cout << S.size() << '\n';
		}
		else if (op == "empty") {
			cout << S.empty() << '\n';
		}
		else if (op == "top") {
			if (S.empty()) cout << -1 << '\n';
			else cout << S.top() << '\n';
		}
	}

	return 0;
}

STL에 있는 stack을 이용해서 풀었습니다.

pop, top함수를 호출할 때 스택이 비어있으면 에러가 발생하므로,

empty함수로 스택이 비어있는지 먼저 확인한 후 사용해야 합니다.