[백준] 10773번: 제로 (C언어)

728x90
728x90

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

 

10773번: 제로

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경

www.acmicpc.net

난이도: solved.ac 실버 4

 

 

이번에는 연결 리스트(Linked List)를 이용해 스택을 구현해보았다

 

이전에 배열(Array)를 이용해 풀었던 스택 구현 문제 (아래 링크 참고)

 

https://jangkunstory.tistory.com/2

 

[백준] 10828번: 스택 (C언어)

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 10

jangkunstory.tistory.com

 

 

Linked List로 구현할 때는 push와 pop 모두 Linked List의 head에서 일어난다

 

새로운 노드를 추가할 때 그 노드가 head가 되게 하고

 

노드를 제거할 때는 head에서 꺼내는 식이다

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

typedef struct _Node {
    int data;
    struct _Node* next;
} Node;

typedef struct _Stack {
    Node* head;
} Stack;

int main() {
    int K, i, j;
    int num, sum = 0;
    scanf("%d", &K);

    /* 스택 초기화 */
    Stack stack;
    stack.head = NULL;

    for (i = 0; i < K; i++) {
        scanf("%d", &num);
        if (num == 0) {     // 스택의 Node를 하나 지움 (pop)
            Node* delNode;
            int del;    // 지울 수
            del = stack.head->data;
            delNode = stack.head;

            sum -= del;
            /* 노드 삭제 과정 */
            stack.head = stack.head->next;
            free(delNode);
        }
        else {      // 스택에 Node를 추가 (push)
            sum += num;
            Node* newNode = (Node*)malloc(sizeof(Node));    // 새로운 노드 생성
            newNode->data = num;    // 새로운 노드의 data에 입력 받은 수를 저장
            newNode->next = stack.head;     // 새로운 노드가 이전의 head를 가리키도록 함
            stack.head = newNode;   // 새로운 노드를 새로운 head로 임명
        }
    }
    printf("%d", sum);
    return 0;
}
반응형