프로그래머스 Level 2 : 주식가격 C언어

▶문제 : 코딩 테스트 연습 - 주식가격 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 주식가격

 

▶코드 작성

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

int stack[100000];//스택 -> prices배열의 원소가 아닌 배열 자리를 저장

// prices_len은 배열 prices의 길이입니다.
int *solution(int prices[], size_t prices_len) {
    int *answer = (int *)malloc(prices_len * sizeof(int));
    int top, len = 0;
    for (int i = 0; i < prices_len; i++)
    {
        top = stack[len - 1];//스택 맨 위 값
        while (prices[top] > prices[i] && len > 0)//i값이 top보다 작으면
        {
            answer[top] = i - top;//top의 가격이 안떨어진 시간(초) 저장
            len--;//top제거
            top = stack[len - 1];//다음 스택 맨 위 값
        }
        stack[len++] = i;//배열 자리 저장
    }

    for (int i = 0; i < len; i++) {//스택에 남아있는 배열 자리
        answer[stack[i]] = prices_len - 1 - stack[i];//가격이 안떨어진 시간(초) 저장
    }
    return answer;
}

 

▶해석

스택을 이용하여 가격이 떨어질 때마다 answer배열에 저장하고 저장한 스택은 버렸다. 가격이 안 떨어진 남은 주식 가격은 스택에 남아있으므로 prices배열의 길이를 뺀 만큼 answer배열에 저장하였다.

 

예를 들어 prices={1,2,3,2,3}라고 한다면,

스택에는 1,2,3까지는 안정적으로 저장하므로 배열 자리를 추가하면 stack={0,1,2}가 된다.

prices [3]은 2이므로 현재 스택의 top인 3보다 가격이 떨어진다.

가격이 떨어지지 않은 시간 배열이 answer이므로 top자리에 시간을 저장해야 하니 answer [top]에 저장한다.

가격이 떨어지지 않은 시간은 i-top인데 i=3, top=2이므로 answer [top]=1이다.

그 후 스택 길이를 감소시키고 다음 스택을 top으로 가리킨다.

그럼 stack={0,1} , answer={ , , 1, , }가 된다.

 

반복문이 다 끝나면 stack={0,1,3,4} , answer={ , , 1, , }가 된다.

남은 스택에 있는 것들을 정리하려면 answer배열의 stack [i] 자리에 시간을 저장해야 한다.

prices배열의 마지막까지 남은 주식 가격이므로 prices_len-1에 배열의 자리인 stack [i]을 빼면 떨어지지 않은 시간이 나온다.

주식 가격 prices [0]=1은 처음부터 끝까지 남아있으므로 5-1-0=4가 나온다.

주식 가격 prices [4]=3은 맨 마지막에 들어왔으므로 5-1-4=0가 나온다.