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

백준 온라인 저지(BOJ) 10773번 제로

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

10773번: 제로

* 사용언어 : C언어, C++

 

1. 문제

최대 100,000개의 숫자가 주어짐

0이 나올 경우 가장 최근에 쓴 수를 지우고, 아니면 해당 수를 씀

최종으로 남아있는 수들의 총합을 출력

 

2. 풀이

기본적인 Stack 구조를 활용하면 간단하게 풀 수 있는 문제입니다. (LIFO)

 

우선 Stack을 1차원 배열로 선언하고

해당 배열에서 사용한 가장 큰 index를 top이라고 지정했습니다.

그리고 top을 +1 or -1 하면서 해당 위치에서만 값을 넣거나 빼게 했습니다.

 

K개의 명령을 모두 마친 후에는 sum이라는 변수에 i부터 top까지의 숫자들을 더해서 출력했습니다.

숫자의 총합은 2^31 - 1 보다 작거나 같으므로 int형 변수로 충분합니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
10773_제로
1500KB	12ms
*/
#include <cstdio>

const int LM = 100000;
int st[LM], top = -1, k, n, sum;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &k);
	while (k--) {
		scanf("%d", &n);
		if (n) st[++top] = n;
		else --top;
	}

	for (int i = 0; i <= top; ++i) sum += st[i];

	printf("%d\n", sum);
	return 0;
}