(매일 BOJ) C++ 10773번 제로

이번 문제는 실버 4 난이도의 10773번 제로문제이다.

접근법

정수 K의 수가 최대 100,000 이기에 vector 나 배열을 사용하면 push  & sum 과정에서 시간 복잡도가 O(n)이기에 O(n^2)가 되어 TLE가 발생하는 것을 확인할 수 있었다. 따라서 큐 혹은 스택 둘 중 하나를 사용해야 하는데, 가장 최근에 쓴 수를 지우는 동작을 반복하기 때문에 선입선출 구조의 큐보다 스택이 알맞는 것을 확인할 수 있었다.

 

아래는 작성한 코드이다.

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

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    stack<int> s;
    int N;
    cin >> N;
    for (int i  = 0; i < N; i++){
        int temp;
        cin >> temp;
        if (temp == 0) {
            s.pop();
        }
        else s.push(temp);
    }
    int sum = 0;
    while (!s.empty()){
        sum += s.top();
        s.pop();
    }
    cout << sum;

}