[프로그래머스] 주식가격 문제 C언어 스택 활용한 풀이

 

 

나중에 여유가 생기면 다시 푸는 걸로...ㅠ

 

1. Node, Stack, push, pop, getTop 정의해주기

 

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define INF 99999999;

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

typedef struct Stack {
    Node *top;
    int count;
} Stack;

void push(Stack *stack, int data) {
    Node *node = (Node*) malloc(sizeof(Node));
    node -> data = data;
    node -> next = stack -> top;
    stack -> top = node;
    stack -> count++;
}

int pop(Stack *stack) {
    if (stack -> top == NULL) {
        return -INF;
    }
    
    Node *node = stack -> top;
    int data = node -> data;
    stack -> top = node -> next;
    stack -> count--;
    free(node);
    return data;
}

int getTop(Stack *stack) {
    if (stack -> top == NULL) {
        return -INF;
    }
    Node *node = stack -> top;
    int data = node -> data;
    return data;
}

배운 대로 아주 정석적인 풀이..

 

2. 문제 해결하기

 

int* solution(int prices[], size_t prices_len) {
    int* answer = (int*)malloc(sizeof(int)*prices_len);
    Stack stack;
    stack.top = NULL;
    stack.count = 0; 
    
    // 시간i를 돌면서 시간i를 stack에 넣어줌.
    for (int i = 0; i < prices_len; i++) {
        // 스택에 넣기 전 이전가격보다 작으면 이전시간i pop하고 지금 answer에 넣어줌
        if (stack.top && prices[getTop(&stack)] > prices[i]) {
            int temp = pop(&stack);
            answer[temp] = i - temp;
        } 
        push(&stack, i);
    }
    
    while (stack.top) {
        int temp = pop(&stack);
        answer[temp] = prices_len - temp - 1;
    }
     
    return answer;
}

 

(1) answer를 동적 메모리 할당시켜주고, stack을 초기화한다.

 

(2) 시간 i를 돌면서 시간 i를 스택에 넣어 준다. 단, 스택에 넣기 전 확인할 것이 있다.

- 지금 스택에 넣을 시간 i의 주식 가격이, 기존에 스택의 최상단 시간(getTop(&stack))의 주식 가격(prices[getTop(&stack)])보다 작은 경우(주가 하락한 경우)를 고려한다.

        if (stack.top && prices[getTop(&stack)] > prices[i]) {
            int temp = pop(&stack);
            answer[temp] = i - temp;
        }

주가가 하락한 경우, 원래 가격이었을 시점과 하락한 지금 시점 i의 차이를 구해야 하기 때문에 i - temp로 계산한다.

 

 

push(&stack, i);

그리고 주가 하락에 관계없이 스택에 시간 i는 계속 넣어준다.

 

    while (stack.top) {
        int temp = pop(&stack);
        answer[temp] = prices_len - temp - 1;
    }

주가 하락한 경우를 다 고려한 후 스택에 남은 값들을 하나씩 빼면서 answer에 시간(인덱스) 별로 주가 안 떨어지고 유지된 시간을 계산해서 넣어준다.

 

하 5시간 동안 붙잡고 있었음..

 

 

문제 링크