[프로그래머스] Lv2. 주식 가격- JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 주식 가격

문제

📌 내가 생각한 풀이

stack을 이용하여 인덱스를 넣어주고, 해당 인덱스의 값보다 작은 값이 나오면 빼서 arr에 넣어주자.

1. 0~length까지 for문을 돌면서 stack에 해당 인덱스를 push
2. 스택의 마지막 요소가 해당 인덱스 요소보다 클 경우 stack에서 pop한 뒤, arr에 값을 넣어주자.
3. pop되지 않은 원소들은 자기보다 작은 값이 없다는 뜻이므로, prices.length-1-해당인덱스번호로 값을 넣어주자.

function solution(prices) {
    let stack = [];
    let arr = new Array(prices.length).fill(0);
    for(var i= 0; i<prices.length; i++){
        while(stack.length && prices[stack.at(-1)] > prices[i]){
            let popped = stack.pop();
            arr[popped] = i-popped;
        }
        stack.push(i);
    }
    while(stack.length){
        let popped = stack.pop();
        arr[popped] = prices.length-1-popped
    }

    return arr
}

📌 느낀점

2중 for문을 사용하면 시간초과가 나는 문제였다. 따라서, for문 한번과 while문 한번을 이용해 O(N+M)시간을 만들어서 풀자.