10773: 제로

-Class2 : Silver 4

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

10773번: 제로

 

-결과

 

-코드

#include <stdio.h>
#include <string.h>

int main() {
    int k, a;
    int top = 0;
    long long int n = 0;
    int stack[100001];

    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        scanf("%d", &a);
        if (a > 0) {
            top += 1;
            stack[top] = a;
            n += a;
        }
        else if (a == 0) {
            n -= stack[top];
            stack[top] = 0;
            top -= 1;
        }
    }
    printf("%d", n);
}

 

-풀이

이 문제는 자료구조에서 배운 스택의 개념을 이용해서 풀 것이다.

스택(Stack)

스택은 Last in First Out (LIFO) 구조로, 프링글스 통과 같은 구조이다. 즉, 한 쪽 끝에서만 자료를 넣다 뺐다 할 수 있는 자료구조이다. 

먼저 스택에서 제일 위에 있는 데이터인 top를 우리는 0으로 가정하고 갈 것이다.

배열의 크기는 첫 번째 줄에 주어지는 정수 k가 십만 이하라고 문제에서 가정하므로 십만1로 잡는다.

 

먼저 k를 입력받고 반복문을 실행한다.

그 반복문은 0이 아닌 정수 a를 입력받으면, 배열 스택의 top에 a가 저장되고 top += 1이 되도록 한다. 또 합인 n에 a값을 더한다.

만약 입력받은 a가 0이라면, n에서 직전에 입력받았던 a인 top를 빼고 배열 스택의 top도 0으로 리셋하고 top -= 1을 한다.