05 스택

Algorithm/baekjoon

05 스택

쿠뱃봉 2022. 1. 26. 18:59

1. 백준 10773

10773번: 제로

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경

www.acmicpc.net

(1) 소스코드

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

int main() {

	int len;
	cin >> len;

	stack<int> s;
	while (len) {
		int element;
		cin >> element;
		if (element == 0) {
			s.pop();
		}
		else {
			s.push(element);
		}
		len--;

	}
	int sum = 0;
	while (s.size()) {
		sum += s.top();
		s.pop();

	}
	cout << sum;


}

(2)백준 1874

1874번: 스택 수열 (acmicpc.net)

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

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

	bool valid = true;
	int len;//8
	cin >> len;

	int n = 1;
	stack<int> s;
	vector<string>result;
	

	int element;
	cin >> element;
	for (int i = 0; i < element; i++) {
		s.push(n);
		result.push_back("+");
		
		n++;
	}
	s.pop();
	result.push_back("-");
	len--;
	while (len) {
		int element2;
		cin >> element2;
		if (s.empty()) {
			if (n == element2) {
				s.push(n);
				s.pop();
				n++;
				result.push_back("+");
				result.push_back("-");
			}
			//else if(n < element2) {
			else{
				while (n <= element2) {
					s.push(n);
					result.push_back("+");
					n++;
				}
				s.pop();
				result.push_back("-");
			
			}
		}
		else if (s.top() == element2) {
			s.pop();
			result.push_back("-");
		
		}
		else if (element2 > s.top()) {
			while (n <= element2) {
				s.push(n);
				n++;
				result.push_back("+");
			}
			s.pop();
			result.push_back("-");
		}
		else {
			valid = false;
			
		}

		len--;
	}


	if(!valid){
		cout << "NO";
	}
	else {
		for (int i = 0; i < result.size(); i++) {
			cout << result[i] << "\n";
		}
		
	}
	return 0;
}

c++ 에서 시간초과가 난다?

->endl을 썼는지 확인해볼 필요가 있음!!

endl을 "\n"으로 바꿔서 쓰기!

3. 백준 2493

무려 티어가 골드5....!!

2493번: 탑 (acmicpc.net)

2493번: 탑

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1

www.acmicpc.net

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>


using namespace std;

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

	vector<int> v;
	int n;
	scanf("%d",&n);

	vector<int> answerv(n);

	for (int i = 0; i < n; i++) {
		int element;
		scanf("%d",&element);
		v.push_back(element);
	}

	int max = 0;
	int flag = 0;
	for (int j = n - 1; j >=1; j--) {
		for (int k = j - 1; k >= 0; k--) {
			max = v[j];
			if (v[j] < v[k]) {
				max = v[k];
				answerv[j] = k + 1;
				flag = 1;
				break;
			}
		
		}
		if (flag == 0) {
			answerv[j] = 0;
		}
	}

	answerv[0] = 0;

	for (int m = 0; m < answerv.size(); m++) {
		printf("%d ",answerv[m]);
	}



}

시간초과난 코드다...

이래서 골드5 인거겠지..

나중에 할래