문제

BOJ 10773, 제로

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 정수가 "0"일 경우 가장 최근에 쓴 수를 지우고 계산하므로 stack 자료구조를 사용한다.

개선

코드

시간복잡도

• $O(N)$

C++

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int k;
	cin >> k;
	stack<int> s;
    int ans = 0;
	while (k--) {
		int num;
		cin >> num;
		if (num) {
			s.push(num);
            ans += num;
			continue;
		}
        ans -= s.top();
		s.pop();
	}
	cout << ans;
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine());
        Stack<Integer> s = new Stack<>();
        int ans = 0;
        for (int i = 0; i < k; i++) {
            int num = Integer.parseInt(br.readLine());
            if (num > 0) {
                s.push(num);
                ans += num;
                continue;
            }
            ans -= s.peek();
            s.pop();
        }
        System.out.println(ans);
        br.close();
    }
}