Leetcode - 121. Best Time to Buy and Sell Stock - Easy

 

오늘 문제는 숫자로 된 배열을 입력값으로 받고 그 숫자들이 매일 매일의 주식 가격이라고 생각하고 가장 큰 수익을 얻는 다면 그 수익은 얼마가 될까 입니다.

 

7,1,5,3,6,4 가 입력값이라면

 

7에 1에 팔면 -6이 되겠죠.

1에 사서 6에 팔면 +5가 되구요.

1에 사서 7에 팔 수는 없죠. 내일 사서 오늘 팔 수는 없으니까요.

 

즉 산 날은 항상 판 날보다 앞서야 됩니다.

 

Example 2를 보면 만약 수익을 낼 수 있는 상황이 아니면 Output은 0가 되어야 합니다.

어짜피 사고 팔면 마이너스이니까 아예 매매를 하지 않는 상황이 최선이 되는 것이죠.

매매를 하지 않으면 수익이나 손해 없이 0이 되니까요.

 

그렇게 어려운 문제는 아닙니다.

 

이중 for 문을 만들어서 계산하면 되겠죠.

 

우선 바깥의 for 문은 입력 된 배열의 크기만큼 돌려주세요.

안의 for 문은 각 숫자마다 그 이후의 값들 크기 만큼 돌려 줍니다. (미래에 사서 과거에 팔 수는 없으니까요)

 

이렇게 돌려주면 뒤의 숫자에서 앞의 숫자를 계속 빼 주고 그 중 가장 큰 값을 구하면 가장 높은 수익이 됩니다.

 

코드는 아래와 같습니다.

 

class Solution {
    public int maxProfit(int[] prices) {
        // buy on each day
        // find largest difference by selling on some day in buyDay's future
        int largestDifference = 0;
        
        for(int buyDay = 0; buyDay < prices.length; buyDay++) {
            for(int sellDay = buyDay +1; sellDay < prices.length; sellDay++) {
                int currentDifference = prices[sellDay] - prices[buyDay];
                if(currentDifference > largestDifference) {
                    largestDifference = currentDifference;
                }
            }
        }
        return largestDifference;
    }
    // time complexity = O(n^2)
    // space complexity = O(1)
}

 

이건 time complexity가 n의 제곱입니다.

모든 아이템을 대상으로 두번 루프를 돌리니까 그렇게 됩니다.

그러면 input 값의 크기가 크다면 시간이 엄청 걸리겠죠.

 

실제로 이 코드로 submit 하면 time limit exceed 가 나옵니다.

(입력되는 배열의 크기가 그렇게 크지 않다면 제대로 돌아 갑니다.)

 

 

그러면 이중 루프를 사용하지 않고 이 문제를 풀 수 있을 까요? Time complexity를 줄이기 위해서요.

 

배열의 모든 아이템을 비교해 보는게 아니라 가장 낮은 값일 때만 비교해 볼 수 있겠죠.

즉 for 문을 돌리면서 해당 값이 이전 값보다 작으면 계산 하는 겁니다.

 

Integer.MAX_VALUE는 Integer에서 가장 큰 숫자 입니다.

이 값부터 시작해서 for 문에서 그 값보다 더 작으면 minSoFar에 그 값을 넣습니다.

그 다음에도 더 작은 수이면 minSoFar에 넣고 그렇지 않으면 계산을 합니다.

즉 판 값이 산 값보다 더 크면 계산을 하는 겁니다.

계산 공식은 largestDifference 하고 나중 숫자에서 minSoFar (이전 숫자)를 뺀 값 중 더 큰 값을 largestDifference에 넣는 겁니다.

 

이렇게 되면 수익을 올리면 계산에 들어가서 더 큰 수익이 largestDifference에 들어가는 겁니다.

수익이 하나도 나지 않는다면 처음 pargestDifference에 할당 되었던 0이 return 되겠죠.

 

이 경우 time complexity는 O(n) 이 됩니다. For 문이 한번만 모든 아이템에 대해 돌기 때문에 아이템 갯수 만큼만 돕니다.

 

이렇게 하면 runtime과 memory 결과는 아래와 같습니다.

 

소스 코드는 아래와 같습니다.

 

class Solution {
    public int maxProfit(int[] prices) {
        // keep track of the best buy day so far
        // keep track of the largest difference so far
        
        int largestDifference = 0;
        int minSoFar = Integer.MAX_VALUE;
        
        for(int i = 0; i < prices.length; i++) {
            if(prices[i] < minSoFar) {
                minSoFar = prices[i];
            } else {
                largestDifference = Math.max(largestDifference, prices[i] - minSoFar);
            }
        }
        return largestDifference;
    }
    // time coplmexity = O(n)
    // space complexity = O(1)
}