10773 - 제로 #스택, #자료 구조, #문자열

10773 - 제로 (https://www.acmicpc.net/problem/10773)
알고리즘 분류 : 구현, 자료 구조, 문자열, 스택
시간 제한 : 1 초

 

스택으로 값을 계속 채우다가, 0이 들어오면 pop()으로 가장 최근 값을 날리고, 숫자가 모두 입력된 후 총합을 출력하면 되는 문제이다.

 

나는 처음 문제를 구현할 때 스택 대신 가장 최근 값만을 기록하는 방식을 사용했다. 

#include <cstdio>

using namespace std;

int main()
{
    int late;
    int n;
    int input;
    long long int total;

    scanf("%d", &n);

    for(int i=0;i<n;i++)
    {
        scanf("%d", &input);
        if (input == 0)
        {
            total -= late;
        } else {
            late = input;
            total += late;
        }
    }

    printf("%lld", total);
}

total이 2의 23승보다 작은 정수이기 때문에 long long int로 선언했다.

이 방법의 문제점은 0이 연속으로 두번 들어올 때 두번째로 늦게 들어온 값을 알 수 없다는 것이다.

#include <cstdio>
#include <stack>

using namespace std;

int main()
{
    stack<int> st;
    int n;
    int input;
    long long int total = 0;

    scanf("%d", &n);

    for(int i=0;i<n;i++)
    {
        scanf("%d", &input);
        if (input == 0)
        {
            st.pop();
        } else {
            st.push(input);
        }
    }

    while(!st.empty())
    {
        total += st.top();
        st.pop();
    }

    printf("%lld", total);
}

 

그래서 스택을 통해 값을 모두 저장하고, 입력이 끝나면 스택 안에 들어있는 값들을 총합에 더하여 출력하는 방식으로 바꿨다.