[C/Python] 백준 10828번 - 스택

매미·2024년 6월 27일

백준

목록 보기

6/13

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

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.

push X: 정수 X를 스택에 넣는 연산이다.

pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

size: 스택에 들어있는 정수의 개수를 출력한다.

empty: 스택이 비어있으면 1, 아니면 0을 출력한다.

top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

발상

< C언어 >
main()에다 다 넣으면 정신없을 거 같으니 함수를 여러 개 나눠야겠다.
스택 값 초기화를 -1로 해서 NULL 역할 하게끔 해야지
< Python >
시간 제한이 0.5초이니 input() 말고 sys.stdin.readline()으로 입력 받아야겠다.

Clang (배열)

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

void top(int* arr, int cnt) {
    if (cnt>0)
        printf("%d\n", arr[cnt-1]);
    else
        printf("%d\n", -1);
}
void empty (int* arr, int n) {
    int cnt=0;
    for (int i=0; i<n; i++) {
        if (arr[i]!=-1)
            cnt++;
    }
    if (cnt>0)
        printf("0\n");
    else
        printf("1\n");
}
void size(int* arr, int n) {
    for (int i=0; i<n; i++) {
        if (arr[i]==-1) {
            printf("%d\n", i);
            break;
        }
    }
}
int pop(int* arr, int cnt) {
    if (cnt>0) {
        printf("%d\n", arr[cnt-1]);
        if (arr[cnt-1]!=-1) {
            arr[cnt-1]=-1;
            cnt--;
        }
    }
    else
        printf("-1\n");
    return cnt;
}
void push(int* arr, int cnt) {
    int input;
    scanf("%d", &input);
    arr[cnt]=input;
}
int stack(int n, int* arr) {
    char input[6];
    int cnt=0;
    for (int i=0; i<n; i++) {
        scanf("%s", input);
        if (strcmp("push", input)==0) {
            push(arr, cnt);
            cnt++;
        }
        if (strcmp("pop", input)==0)
            cnt=pop(arr, cnt);
        if (strcmp("size", input)==0)
            size(arr, n);
        if (strcmp("empty", input)==0)
            empty(arr,n);
        if (strcmp("top", input)==0)
            top(arr,cnt);
    }
}
int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i=0; i<n; i++)
        arr[i]=-1;
    stack(n, arr);
    return 0;
}

재발상

배열을 활용해서 푸는 것도 맞긴 하지만 너무 비효율적.
Linkedlist를 활용해보자.

Clang (Linkedlist)

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

struct stack{
    int data;
    struct stack* next;
};

struct stack* tail = NULL;
struct stack* head = NULL;

void push(int num) {
    struct stack* newnode = (struct stack*)malloc(sizeof(struct stack));
    newnode->data=num;
  	newnode->next=NULL;

    if (tail == NULL) {
        tail = newnode;
        head = newnode;
    }
    else {
        tail->next = newnode;
        tail = newnode;
    }
}
void pop() {
    if (tail!=NULL) {
        printf("%d\n", tail->data);

        struct stack* tmp = head;
        if (head!=tail) {
            while (tmp->next!=tail)
                tmp = tmp->next;
            tail = tmp;
        }
        else
            tail = NULL;
    }
    else
        printf("-1\n");
}
void size() {
    int size=0;
    struct stack* tmp = head;
    while (tmp != NULL) {
        size++;
        tmp = tmp->next;
    }
    printf("%d\n", size);
}
void empty() {
    if (tail!=NULL)
        printf("0\n");
    else
        printf("1\n");
}
void top() {
    if (tail!=NULL) {
        printf("%d\n", tail->data);
    }
    else
        printf("-1\n");
        
}
int input(int n) {
    char input[6];
    int num;
    scanf("%s", input);

    if (strcmp(input,"push")==0) {
        scanf("%d", &num);
        push(num);
    }
    if (strcmp(input,"pop")==0)
        pop();
    if (strcmp(input,"size")==0)
        size();
    if (strcmp(input,"empty")==0)
        empty();
    if (strcmp(input,"top")==0)
        top();
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i=0; i<n; i++)
        input(n);
    
    struct stack* current=(struct stack*)malloc(sizeof(struct stack));
    current = head;
    while (current != NULL) {
        struct stack* tmp = current;
        current = current->next;
        free(tmp);
    }
    return 0;
}

Python

import sys

n = int(sys.stdin.readline())
stack = []
for i in range(n):
    Sinput = sys.stdin.readline().split()
    if Sinput[0]== 'push':
        stack.append(Sinput[1])
    elif Sinput[0]== 'pop':
        try:
            print(stack[-1])
            stack.pop(-1)
        except:
            print(-1)
    elif Sinput[0]== 'size':
        print(len(stack))
    elif Sinput[0]== 'empty':
        if len(stack)==0:
            print(1)
        else:
            print(0)
    elif Sinput[0]=='top':
        try:
            print(stack[-1])
        except:
            print(-1)