[백준(BOJ) 10773번] 제로 (C++)

문제 링크

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

 

문제 정보

입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

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

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.

 

풀이

 정수가 0인 경우에 가장 최근에 쓴 수를 지워야 하는 문제다. 스택은 LIFO 구조를 가지고 있으므로 스택을 이용하면 해결 할 수 있다는 것을 알 수 있다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int k;
	cin >> k;
	
	stack<int> S;
	
	int sum = 0;
	while (k--) {
		int num;
		cin >> num;
		
		if (num == 0) {
			sum -= S.top();
			S.pop();
		} else {
			sum += num;
			S.push(num);
		}
	}
	
	cout << sum;
	
	return 0;
}