[프로그래머스 level 2] 주식가격 (스택 / 큐)

• 출처 : 프로그래머스
• 사용 언어 : C
• 알고리즘 : 스택/큐

---

1. 문제

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

---

2. 알고리즘 띵킹!

• 배열의 길이만큼 for문을 돌리며 현재 인덱스 데이터보다 다음 인덱스 데이터가 같거나 크면 cnt++ 를 해주고, 작으면 cnt를 그 인덱스의 데이터로 저장한다.

3. 해결 코드

• 이중 반복문을 활용해서 풀었다.

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

// prices_len은 배열 prices의 길이입니다.
int* solution(int prices[], size_t prices_len) {
    // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요.
    int* answer = (int*)malloc(sizeof(int)*prices_len+1);

    for(int i=0; i<prices_len; i++){
        int cnt =0;
        for(int j=i; j<prices_len-1; j++){
            if(prices[i]<=prices[j])    cnt++;
            else    break;
        }
            prices[i]=cnt;
    }
    memcpy(answer, prices, sizeof(int)*prices_len);
    return answer;
}

 

4. 해결능력up! 되짚어보기 

이중 반복문을 활용했기 때문에 시간복잡도가 O(n^2) 이다.

스택을 활용하면 시간복잡도를 O(n)으로 만들수 있다.

스택에 대한 개념은 알지만 프로그래밍을 통해 제대로 써본적이 없다.

다른 언어를 써서 스택으로 푼 코드를 참고하여 C로 짜보아야 겠다.

---

* 개인적인 학습 목적으로 작성한 글이기에 내용에 잘못된 정보가 있을 수 있습니다.

* 문제 출처 - https://programmers.co.kr/learn/courses/30/lessons/42584