42584. 주식가격

프로그래머스 42584번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

코딩테스트 연습 - 주식가격 | 프로그래머스 스쿨

풀이

아이디어

가격이 떨어지는 시점을 만났을 때, 스택에 쌓여 있는 이전 데이터들을 역순으로 처리해서 답을 구하면 O(N)으로 해결할 수 있다.

처음에는 이렇게 풀었는데, 하나의 테스트 케이스에서 시간 초과가 발생했다.

function solution(prices) {
    const pricesData = prices.map((price, day) => ({price, day}));
    const stack = [];
    const answer = Array(prices.length).fill(0);

    for (const {price, day} of pricesData) {
        if (stack.length === 0) stack.push({price, day});
        else {
            while (stack.length !== 0) {
                const top = stack[stack.length - 1];
                if (top.price <= price) break;
                stack.pop();
                answer[top.day] = day - top.day;
            }
            stack.push({price, day});
        }
    }

    for (const {price, day} of stack) {
        answer[day] = prices.length - day - 1;
    }

    return answer;
}

알고리즘 자체는 O(N)으로 푸는게 맞았는데, 이리저리 자료구조를 바꿔보니 pricesData를 하나 더 만든 것이 원인이었다. 인덱스와 가격을 함께 묶어서 관리해야 할 것 같아서 객체 배열을 하나 더 만들었던 것인데, 이렇게 하니 배열 할당, for...of 구조분해 같이 불필요한 시간들이 더 쓰인 것이 문제였다.

prices가 어차피 인덱스가 유지되는 배열이기 때문에, 그냥 인덱스만 저장하는 것으로도 충분했다. 그래서 아래처럼 수정했고 통과할 수 있었다.

function solution(prices) {
    const stack = [];
    const answer = Array(prices.length).fill(0);

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

    while (stack.length > 0) {
        const top = stack.pop();
        answer[top] = prices.length - top - 1;
    }

    return answer;
}

이렇게 기준이 빡빡한게 실화라니…