Level 2 ) 주식 가격

문제 설명

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

제한사항

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

입출력 예

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

입출력 예 설명

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

처음 생각한 풀이

ex. [1, 2, 3, 2, 3]

1. (prices 길이 - 1) 크기의 0으로 채워진 배열 만들기
   [0, 0, 0, 0]
2. 현재 숫자보다 가격이 같거나 큰 경우의 개수세서 넣기
   ex. 1 : 4개 => [4, 0, 0, 0]
   ex. 2 : 3개 => [4, 3, 0, 0]
   ex. 3 : 1개 => [4, 3, 1, 0]
   ex. 2 : 1개 => [4, 3, 1, 1]
3. 마지막은 더 이상 비교할게 없어 항상 0이므로 마지막에 0을 push한다.
   [4, 3, 1, 1, 0]

⭐️ 잘못 이해했던 부분
처음부터 끝까지 같거나 큰 값의 개수를 다 세면 된다고 생각했는데, 중간에 더 작은 값이 나오는 경우 그 뒤는 세지 않고 break 해야 한다. (가격이 떨어지지 않고 유지된 기간을 구해야 함!)

수정된 풀이

입력값 〉 [1, 3, 4, 2, 3]
기댓값 〉 [4, 2, 1, 1, 0]

위 케이스를 처음 생각한 방식으로 풀면 [4, 2, 2, 1, 0] 이 나와야 한다. 3초일 때 4는 2와 3보다 크므로 2개를 세기 때문이다. 하지만 실제로는 4 다음 2가 나오기 때문에 1초까지만 가격이 떨어지지 않는 것으로 보아야 한다.

테스트케이스는 다 통과하고 효율성 테스트 3/5 통과.

function solution(prices) {
    let answer = Array.from({length: prices.length - 1}).fill(0)
    for(let i=0;i<prices.length-1;i++){
        for(let j=i+1;j<prices.length;j++){
            if(prices[i] > prices[j]){
                answer[i]++;
                break;
            }else if(prices[i] <= prices[j]){
                answer[i]++
            }
        }
    }
    answer.push(0);
    return answer;
}

배열을 미리 채우지 않고 temp 변수를 만들어 단축시키니 효율성 테스트도 통과했다.

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

다른 풀이

스택과 dp를 활용한 풀이

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

    prices.forEach((price,index) => {
        while(stack.length && prices[stack[stack.length - 1]] > price){
            const tempIndex = stack[stack.length - 1];
            dp[tempIndex] = index - tempIndex; 
            stack.pop();
        };
        stack.push(index); 
    });

    return dp;
}