https://www.acmicpc.net/problem/10773
문제
> 재민이가 장부를 쓰고 재현이가 돈을 불러준다.
> 재현이가 자주 수를 잘못 불러주는데 그때마다 0을 외쳐서 재민이가 썼던수를 지우게 시킨다.
> 재민이가 모든 수를 받아적고 그 수의 합을 구하려고 한다.
> 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)
이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가진다.
> 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.접근
"0을 외치면 가장 최근의 수를 지운다" 라는 말은 스택의 구조라는걸 유추할 수 있다. 따라서 입력으로 수를 받는데 0이 들어오면 pop 아니면 push해준뒤 스택에 담긴 수의 합을 구한다.
문제해결
> 스택을 하나 선언해주고 입력받은 K만큼while문을 돌린다.
i에 들어온 수를 입력받는데 0인지 검증하여 0이면 pop()을 아니라면 push(i)를 해 수를 넣는다.
> 끝나면 스택에 수가 안들어 있을 때까지 while문을 통해 sum에 각 스택의 값을 누적하며 제거해준다. 그 합을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int K;
cin >> K;
stack<int> s;
while (K--)
{
int i;
cin >> i;
if (i == 0)
s.pop();
else
s.push(i);
}
int sum = 0;
while(!s.empty())
{
sum += s.top();
s.pop();
}
cout << sum << '\n';
}
후기
스택의 기본기를 다지는 문제였다.
입력을 받으며 동시에 sum을 처리할 수 있을거같다. 이를 고민해보자.
