[백준] 2493번 탑 (= tower) - 재우스 프로그래밍 (C 언어)

문제 링크 :www.acmicpc.net/problem/2493

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

#define DEBUG 1
#define MAX_STACK_SIZE 500000
#define MAX_TOWER_HEIGHT 10000000

typedef struct _node {
    int height;
    int position;
} Node;

typedef struct _stack {
    Node mem[MAX_STACK_SIZE];
    int Top;
} stack;

bool empty(stack *);
void pop(stack *);
void push(stack *, Node *);
size_t size(stack *);
Node *top(stack *);
void initStack(stack *);

int main(void)
{
    int N;    //tower의 개수
    //0에는 최대 크기의 벽이 있다고 생각하고 1부터 입력 받은 tower의 높이 저장
    int arrInputTower[MAX_STACK_SIZE + 1];
    int arrResultTower[MAX_STACK_SIZE + 1];
    stack *st = (stack *)malloc(sizeof(stack));
    Node tempNode;

    scanf("%d", &N);
    //제일 앞의 타워에 부딪히면 수신할 탑이 없는거로 인식
    arrInputTower[0] = MAX_TOWER_HEIGHT + 1;
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arrInputTower[i]);
    }

    for (int i = N; i >= 0; i--) {
        //stack이 비어있으면 현재 높이와 위치를 push하고 다음 for문으로
        while (!empty(st)) {
            //stack의 top이 현재 높이의 타워에 수신된다면 result에 저장
            if (top(st)->height < arrInputTower[i]) {
                arrResultTower[top(st)->position] = i;
                pop(st);
            }
            //stack의 top이 현재 높이의 타워에 수신되지 않는다면(stack의 top 높이보다 현재 높이가 더 낮다면) 더 이상 탐색할 필요가 없음
            //(과거에 stack에 쌓인 높이보다 낮은 높이만 stack에 쌓이기 때문)
            else {
                break;
            }
        }
        tempNode.height = arrInputTower[i];
        tempNode.position = i;
        push(st, &tempNode);
    }

    for (int i = 1; i <= N; i++) {
        printf("%d ", arrResultTower[i]);
    }

    free(st);
    return 0;
}

bool empty(stack *st)
{
    if (st->Top == -1) { return true; }
    else { return false; }
}
void pop(stack *st)
{
    st->mem[st->Top].height = 0;
    st->mem[st->Top--].position = 0;
    return;
}
void push(stack *st, Node *node)
{
    st->mem[++st->Top].height = node->height;
    st->mem[st->Top].position = node->position;
    return;
}
size_t size(stack *st) { return (size_t)(st->Top + 1); }
Node *top(stack *st)
{
    Node *tempNode = (Node *)malloc(sizeof(Node));
    (*tempNode) = st->mem[st->Top];
    return tempNode;
}
void initStack(stack *st)
{
    for (int i =  0; i < MAX_STACK_SIZE; i++) {
        st->mem[i].height = 0;
        st->mem[i].position = 0; 
    }
    st->Top = -1;
    return;
}