C++ 백준 10773 제로

백준 10773

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

10773번: 제로

풀이 전 나의 생각

재현이가 0을 외칠 때마다 최근에 재민이가 쓴 수를 지우고

나온 장부의 최종 합의 값을 구해내야한다.

 

조건

- (1 ≤ K ≤ 100,000)

- 정수는 0에서 1,000,000 사이의 값

 

과정

K가 10만회 까지 나올 수 있으니 1중 for문을 사용하여 해결하면 될 것 같다.

주어지는 정수는 int 타입으로 충분할 것 같다.

 

그러면 0을 외칠 때마다 최근에 있는 값을 지워야 하는데 

이 의미는 0이 나온 바로 이전의 값을 지워야 한다는 의미다.

 

그럼 가장 최근에 나온 값을 삭제 해주는 구조를 생각해보면 

후입선출(LIFO)의 형식을 가진 스택이 있다.

 

따라서 0이 나올 때마다 최근 값을 빼주는 로직을 스택을 이용하여 문제를 해결하면 된다.

 

1. 현재 받은 정수값이 0이면 최근 값을 빼주고 아니라면 값을 넣어준다.

for (int i = 0; i < K; i++)
	{
		int val;
		cin >> val;

		if (val == 0) vec.pop_back();
		else vec.push_back(val);
	}

실제로 스택 자료구조를 사용해도 되지만 벡터도 끝에 값을 넣고 끝 값을 빼는

구조기 때문에 문제를 해결하는데 상관없다. 

 

2. 최종적으로 나온 값을 모두 더해준다.

for (int i = 0; i < vec.size(); i++)
	{
		ans += vec[i];
	}

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

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

	int K, ans = 0;

	cin >> K;

	vector<int>vec(K);

	for (int i = 0; i < K; i++)
	{
		int val;
		cin >> val;

		if (val == 0) vec.pop_back();
		else vec.push_back(val);
	}

	for (int i = 0; i < vec.size(); i++)
	{
		ans += vec[i];
	}

	cout << ans;
}