스택/큐 > 주식가격

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

프로그래머스

 

 

배열이 주어지고 그 각 시점의 가격이 떨어지지 않은 것만 카운트 하면 된다

 

1 = 4번 상승

2 = 3번 상승하거나 보합 

3 = 1번 보합

2 = 1번 상승

3 = 0

 

스택/큐 문제라는데 아직 익숙하지 않아서인가 그냥 푸는게 더 쉽게 구현이 가능해보이는데 

이런식의 접근을 했을 때 예제는 풀리는데 다른 예시들이 통과가 안됨

가격이 떨어졌을 때 2번째 중첩 포문에서의 반복을 중단하고 다음 숫자로 넘어가야 함

2중 포문에 대한 구조적 이해와 숙달이 좀 더 필요함

function solution(prices) {
    let arr = [];
    for (let i = 0; i < prices.length; i++) {
        let count = 0;
        for (let j = i + 1; j < prices.length; j++) {
            count++;
            if (prices[i] > prices[j]) {
                break; // 가격이 떨어지면 반복 중단
            }
        }
        arr.push(count);
    }
    return arr;
}

 

결국 이런식으로 풀어내야 한다.

 

스택/큐를 이용하여 푸는 방법

function solution(prices) {
    let answer = new Array(prices.length).fill(0);
    let stack = []; // 가격의 인덱스를 저장할 스택

    for (let i = 0; i < prices.length; i++) {
        // 스택이 비어있지 않고 현재 가격이 스택의 top에 있는 가격보다 낮을 때
        while (stack.length > 0 && prices[i] < prices[stack[stack.length - 1]]) {
            let top = stack.pop();
            answer[top] = i - top; // 가격이 떨어진 기간 계산
        }
        stack.push(i); // 현재 가격의 인덱스를 스택에 저장
    }

    // 스택에 남아 있는 인덱스에 대해서 가격이 떨어지지 않은 기간 계산
    while (stack.length > 0) {
        let top = stack.pop();
        answer[top] = prices.length - 1 - top;
    }

    return answer;
}

const prices = [1, 2, 3, 2, 3];
console.log(solution(prices)); // [4, 3, 1, 1, 0]