10773) 15. 스택 : 제로(Zero That Out)

문제

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

불러오는 중입니다...

 

풀이

 

1. Linked List Stack 구조를 사용하는 방법

#include "cstdio"

class NODE {
    friend class Stack;
private:
    int m_data;
    NODE* prev, *next;
public:
    NODE();
    NODE(int);
};
NODE::NODE() : m_data(0), prev(NULL), next(NULL) {}
NODE::NODE(int data) : m_data(data), prev(NULL), next(NULL) {}

class Stack {
    friend NODE;
private:
    int count;
    NODE* head, *tail;
public:
    Stack();
    void push(int);
    int pop();
    bool empty();
};
Stack::Stack() : count(0), head(NULL), tail(NULL) {}
void Stack::push(int data) {
    // 정수 X를 스택에 넣는 연산
    NODE* nNode = new NODE(data);
    if(!empty()) {
        // 스택에 값을 추가할 때
        nNode->prev = tail;
        tail->next = nNode;
        tail = tail->next;
    }
    else { tail = head = nNode; }
        // 스택에 처음 넣을 때
    ++count;
}
int Stack::pop() {
    // 스택에서 가장 위에 있는 정수를 빼고 그 수를 출력
    // 아무것도 없으면 -1 출력
    if(!empty()) {
        int data(tail->m_data);
        if(head->next != NULL) {
            NODE* temp = tail->prev;
            temp->next = NULL;
            delete tail;
            tail = temp;
        }
        else {
            delete head;
            head = NULL;
        }
        --count;
        return data;
    }
    return -1;
}
bool Stack::empty() {
    // 스택이 비어있으면 1, 아니면 0 출력
    if(this->head == NULL) return true;
    return false;
}

int main() {
    int repeat(0), data(0), sum(0);
    Stack stack;
    
    scanf("%d%*c", &repeat);
    
    for(int i(0); i < repeat; i++) {
        scanf("%d%*c", &data);
        
        if(data != 0) stack.push(data);
        else stack.pop();
    }
    
    while(!stack.empty()) sum += stack.pop();
    printf("%d\n", sum);
    
    return 0;
}

 

2. 동적 배열을 사용하는 방법

#include "cstdio"
#include "stdlib.h"

int* data(NULL);

int main() {
    int repeat(0), idx(0), sum(0);
    
    scanf("%d%*c", &repeat);
    data = (int*)malloc(sizeof(int) * repeat);
    
    for(int i(0); i < repeat; i++) {
        scanf("%d%*c", &sum);
        
        if(sum) data[idx++] = sum;
        else idx--;
    }
    
    sum = 0;
    for(int i(0); i < idx; i++) sum += data[i];
    printf("%d\n", sum);
    
    free(data);
    return 0;
}