[자바 알고리즘 인터뷰] 7장 배열(6) - 주식을 사고팔기 가장 좋은 시점

 
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

 

 
- 한번의 거래로 낼 수 있는 최대 이익을 산출하라 
 
 

풀이 1) 브루트 포스로 계산 

 
- 처음부터 O(n^2)로 사고팔고를 반복하면, 마지막에 최대 이익을 산출할 수 있음
- 타임아웃 
 

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;

        //구매 시점 순회, 처음부터 끝까지 차례대로 반복
        for(int i=0; i<prices.length; i++)
        {
            //판매 시점 순회, 구매 다음부터 끝까지 차례대로 반복
            for(int j=i+1; j<prices.length; j++)
            {
                //판매 시점 가격에서 구매 시점 가격을 뺄 때 가장 높은 금액 찾기
                maxProfit = Math.max(maxProfit, prices[j]-prices[i]);
            }
        }

        return maxProfit;
    }
}

 
 

풀이 2) 저점과 현재 값과의 차이 계산 

 
- 입력값 [8,1,5,3,6,4] 를 그래프로 나타냄 
- 인덱스 1은 저점을 가리키고 있고 인덱스 4는 그 이후의 고점을 가리킨다.

출처: 자바 알고리즘 인터뷰 with 코틀린 저자 : 박상길 <책만>

 
- 현재 값을 가리키는 포인터가 우측으로 이동하면서 이전 상태의 저점을 기준으로 가격 차이를 계산하고, 만약 가격이 클 경우 최댓값을 계속 교체해 나가는 형태로 O(n) 풀이가 가능
 
- 처음 시작할 때는 저점이 얼마인지 알 수 없기 때문에 임시로 첫 번째 값을 저점으로 지정하고 차례대로 우측으로 이동하면서 현재 값과 저점의 차이가 최대 이익인 경우 교체하고, 마지막으로 최대 이익을 정답으로 리턴 
 

class Solution {
    public int maxProfit(int[] prices) {
        //최대 이익은 0, 저점은 임시로 첫 번째 값으로 지정
        int maxProfit = 0, minPrice = prices[0];
        
        //현재 값을 우측으로 차례대로 이동하면서 계산
        for(int price : prices)
        {
            //지금까지 저점 계산
            minPrice = Math.min(minPrice, price);
            //현재 값과 저점의 차이가 최대 이익인 경우 
            maxProfit = Math.max(maxProfit, price-minPrice);
        }

        return maxProfit;
    }
}

2밀리초