[백준 11501번] 그리디 알고리즘 - 주식

✨ 문제 ✨

✨ 정답 ✨

const { count } = require("console");
const fs = require("fs");
const { nextTick } = require("process");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().trim();


// const fs = require('fs'); 
// let input = fs.readFileSync("/dev/stdin").toString().trim();

input = input.split('\n')

const T = +input[0];

const solution = (i) => {
    const N = +input[2 * i + 1];
    let array = input[2 * i + 2].split(' ').map((el) => +el);

    let index=N-1;
    let max=array[index];
    let answer=0;
    while (index>=0){
        if (max<array[index]){
            max=array[index];
        }else{
            answer+=max-array[index];
        }
        index--;
    }

// 시간초과가 난 코드
    // let sorted = array.slice().sort((a, b) => b - a)
    // let eachAnswer = 0;
    // for (let t = 0; t < array.length; t++) {
    //     let maxIndex = array.indexOf(sorted[t])
    //     for (let j = 0; j < maxIndex + 1; j++) {
    //         eachAnswer += sorted[t];
    //         eachAnswer -= array[j]
    //     }
    //     array = array.slice(maxIndex + 1,)
    // }
    return answer;
}

for (let i = 0; i < T; i++) {
    console.log(solution(i));
}

🧵 참고한 정답지 🧵

https://orchemi.github.io/boj%20silver%20ii/BOJ_TD01_11501/

💡💡 기억해야 할 점 💡💡

지긋지긋한 시간초과와 메모리 초과. shift(), while, for 모두 최대한 없애 보았는데도 계속 시간초과와 메모리 초과가 나서 답지를 보았다. Math.max를 사용하지 않고 직접 max값을 찾아보며 푸는 방법도 있다는 것을 깨달았다.