[Node.js] 백준 Javascript 11501 주식

1. 문제

https://www.acmicpc.net/problem/11501

 

2. 풀이과정

😢문제를 보자마자 생각이 든 풀이(시간초과)

1. 날 별 주가 배열에서 최댓값을 찾는다..
2. 최댓값보다 앞에 위치하면서 작은 모든 값을 배열에서 제거 시킨다.
3. 다시 1번으로 돌아가 다음 최댓값을 찾는다.
위 로직을 배열이 빌때까지 반복

최댓값을 계속 다시 찾는 과정에서 문제가 시간초과가 난 것 같다.

 

😃 정답 로직

배열을 역으로 순회하면 그냥 뒤에서 부터 최댓값을 구한다.
순회 중에 현재까지의 가장 비싼 주가가 남는다!
이 가격보다 비싸게 파는 날를 만나기 전까지는 모두 현재까지의 최대 가격으로 팔아주면 최고 익절이다.

최적화 로직:
최대 주가 찾기: 뒤에서부터 현재까지의 주가 중 가장 비싼 날을 찾는다.
이익 계산: 현재 주가와 그 이후의 최고 주가 간의 차이를 이익으로 계산한다.

 

 

3. 자바스크립트 정답 코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

let answer ="";
for(let i = 2; i < input.length; i += 2) {
    answer += calc(i) + "\n";
}
console.log(answer);

function calc(i){
    let stockFlow = input[i].split(' ').map(Number);
    let profit = 0;
    let maxPrice = 0;
    for(let j = stockFlow.length - 1; j >= 0; j--) {
        if (stockFlow[j] > maxPrice) {
            maxPrice = stockFlow[j];
        }
        profit += maxPrice - stockFlow[j];
    }
    return profit;
}

현재 11501문제 node.js로 가장 빠른 코드