프로그래머스 주식가격 (JavaScript)

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

프로그래머스

문제 설명

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

제한사항

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

입출력 예

prices	return
[1, 2, 3, 4, 5]	[4, 3, 1, 1, 0]

입출력 예 설명

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

---

처음 JS로 알고리즘 문제를 풀어보는거라 기본적인 레벨2를 선택해보았다.

`스택/큐` 범주에 들어있는 문제인데, 처음엔 그냥 무식하게 풀어보니 정답이다...?

function solution(prices) {
    var answer = [];
    for(let i = 0; i < prices.length; i++) {
        let sum = 0;
        for(let j = i + 1; j < prices.length; j++) {
            sum++;
            if(prices[i] > prices[j]) break;
        }
        answer.push(sum);
    }
    return answer;
}

 

다시.. 정신차리고 스택으로 풀어보려고 노력해보자

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

1. 스택에는 아직 처리되지 않은 인덱스를 저장
2. 새로운 가격이 들어올 때마다, 스택에 있는 이전 가격과 비교
3. 가격이 떨어졌으면 해당 시점의 기간을 계산하고 스택에서 제거
4. 반복

시간복잡도 비교

크게 달라보이지 않긴 하지만, 확실하게 스택으로 만들었을 땐 O(n)의 시간복잡도를 가지며, 이중반복문은 O(n^2)의 시간복잡도를 가질 것이다!