[JS] 주식 가격

 

 

난이도: Lv. 2

정답률: 58%

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

프로그래머스

 

 

알고리즘

1. 정답 배열을 (주어진 배열 prices의 길이 - 1) 부터 0까지 1씩 감소하는 원소들로 초기화한다.

2. 스택에 삽입할 데이터는 [가격, 인덱스] 형태의 배열이다.

3. 스택 꼭대기에 위치한 원소의 가격이 현재 스택에 삽입할 원소의 가격보다 크면 가격이 떨어졌음을 의미한다. 이 경우 스택을 pop() 하여 몇 초 뒤에 가격이 떨어졌는지 정답 배열을 업데이트한다.

 

 

코드

function solution(prices) {
    const answer = Array.from({ length: prices.length }, (v, i) => prices.length - 1 - i);
    const stack = [];

    for (let i = 0; i < prices.length; i++) {
        while (stack.length && stack[stack.length - 1][0] > prices[i]) {
            const popPrice = stack.pop();
            answer[popPrice[1]] = i - popPrice[1];
        }
        stack.push([prices[i], i]);
    }

    return answer;
}

 

 

주저리

처음 풀었을 때는 정답 배열을 그냥 모두 0으로 초기화하고, 스택에 남아있는 원소들에 대해서만 다시 정답 배열을 업데이트했다. 테스트 케이스는 모두 맞지만 효율성 테스트 2, 4가 시간 초과가 났다. 정말 배열을 딱 한 번만 순회해야 하겠다 싶어서 정답 배열을 애초부터 저렇게 초기화하니까 효율성 테스트도 모두 통과했다.