Codility Lesson9 - MaxProfit

🔍 문제

---

주어진 배열 A의 원소가 한 주식의 가격이라고 생각하고, 배열 A의 index는 날짜라고 생각한다. 따라서 주식의 가격(배열 값)은 날짜(index)에 따라 가격이 변화하는데, 이 중 주식을 사고 팔았을 때 가장 큰 이익을 계산해서 return 하면 되는 문제이다. 만약 이익을 낼 수 있는 경우가 전혀 없고 손해만 난다면 return 0을 해주면 된다.

 

MaxProfit coding task - Learn to Code - Codility

 

✏️ 풀이 - JS

---

이 문제를 brutal force로 푸는 방법 밖에 생각나지 않아, 검색해보다가 Kadane's Algorithm에 대해 알게 되었다. 이 알고리즘에 대한 포스트는 여기로가면 볼 수 있다 👉 Dynamic Programming - Kadane’s Algorithm (카데인 알고리즘)

 

이 알고리즘에서 착안하여, A[i] - A[0] 부터 A[i] - A[i-1]까지 모두 거치면서 maxProfit을 구할 필요가 없이 A[i]가 가질 수 있는 maxProfit값은 A[0]~A[i-1]까지의 값 중에서 가장 작은 값을 뺀 값으로 생각하면 된다. 어떤 index i에 대한 가장 큰 이익은 localMaxProfit 변수로 두고, 이 배열을 통틀어 가장 큰 이익은 globalMaxProfit으로 두어 마지막에 이 값을 return 해주었다.

 

시간 복잡도는 O(N)로 정확도, performance 모두 100%가 나왔다.

function solution(A) {
    if(A.length === 1 || A.length === 0) return 0;

    let minPrice = A[0];
    let localMaxProfit = 0;
    let globalMaxProfit = 0;

    for(let i = 1; i < A.length; i++) {
        localMaxProfit = A[i] - minPrice;
        if(A[i] < minPrice) minPrice = A[i];

        globalMaxProfit = Math.max(localMaxProfit, globalMaxProfit);
    }

    if(globalMaxProfit < 0) return 0; //이익을 보는 경우가 없이, 손해만 나는 경우

    return globalMaxProfit;
}