[프로그래머스/C] 주식가격

 

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

 

 

이중 반복문 사용

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

int* solution(int prices[], size_t prices_len) {
    int* answer = (int*)malloc(sizeof(int) * prices_len);
    int cnt = 0;
    
    for (int i = 0; i < prices_len; i++) {
        cnt = 0;
        for (int j = i + 1; j < prices_len; j++) {
            cnt++;
            if (prices[i] > prices[j])
                break ;
        }
        answer[i] = cnt;
    }
    return answer;
}

 

• 각 시점에서 다음 시점들을 탐색하여 가격이 떨어지지 않은 시간을 세고, 이를 배열에 저장
• 시간 복잡도는 O(n^2)

 

 

스택 사용

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

int* solution(int prices[], size_t prices_len) {
    int *answer = (int*)malloc(sizeof(int) * prices_len);
    int *stack = (int *)malloc(sizeof(int) * prices_len);
    
    int top = 0;
    for (int i = 0; i < prices_len; i++) {
        while (top > 0 && prices[stack[top]] > prices[i]) {	// stack 맨 위 인덱스의 가격 > 현재가격
            answer[stack[top]] = i - stack[top];
            top--;
        }
        stack[++top] = i;
    }
    while (top > 0) {
        answer[stack[top]] = prices_len - stack[top] - 1;
        top--;
    }
    return answer;
}

 

• 스택에는 가격 배열의 인덱스를 저장
• 순회 중인 현재 가격과 스택의 꼭대기(즉, 최근의 가격 인덱스)에 해당하는 주식 가격을 비교하여 현재 가격이 떨어졌다면, 스택에서 해당 인덱스를 꺼내어 기간을 계산하여 answer 에 저장
• 가격이 떨어지지 않으면 스택에 현재 인덱스를 추가
• 배열의 마지막까지 순회한 후에도 스택에 남아있는 인덱스들은 끝까지 가격이 떨어지지 않은 경우이므로, 이를 처리하여 answer에 저장
• 시간 복잡도는 O(n)