JAVA 자료구조 (배열) - 주식을 사고팔기 가장 좋은 시점

주식을 사고팔기 가장 좋은 시점 

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

이 문제는 저점에서 사서 고점에 팔아, 낼 수 있는 최대 이익을 찾는 흥미로운 문제다. 가장 먼저 접근할 풀이법은 당연히 브루트 포스다. 처음부터O(n²)으로 사고팔고를 반복하면, 최대 이익을 산출할 수 있다.

 public int  solution(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 - 저점과 현재 값과의 차이 계산

그림 7-12 현재 값이 우측으로 이동하면서 저점과의 차이 계산

 

입력 값[8, 1, 5, 3, 6, 4]를 그림 7-12와 같이 그래프로 그려보자. 이처럼 값을 그래프로 나열해서 시각화 해보면 대략 어떤 식으로 풀어야 할지 직관이 생길 것이다. index 1은 그래프 에서 최저 점을 가르키고 있고 index 4그 이후의 고점이다. 여기서는 현재 값을 가리키는 포인터가 우측으로 이동하면서 이전 상태의 저점을 기준으로 가격차이를 계산하고, 만약 가격이 클 경우 최대값을 계속 교체해 나가는 형태로 O(n)풀이가 가능할 것 같다. 이 처럼 직접 그림으로 나타내는 시각화 작업을 해보면, 어려운 문제를 맞닥뜨려도 풀이에 대한 직관이 떠오를 수 있다. 

 

public int  solution(int [] prices) {
    int maxProfit = 0, minPrice = prices[0];
    for(int price :prices){
        minPrice = Math.min(minPrice,price);
        maxProfit = Math.max(maxProfit,price - maxProfit);
    }
    
   return maxProfit;
}

 

처음 시작할 때는 저점이 얼마인지 알수 없기 때문에 임시로 첫 번 째 값을 저점으로 지정하고 차례대로 우측으로 이동하면서 현재의 값과 저점의 차이가 최대 이익인 경우 교체하고, 마지막으로 최대 이익을 정답으로 리턴한다.

 

 

[출처 - 자바 알고리즘 인터뷰 with 코틀린 , 저 박상길]

https://www.onlybook.co.kr/entry/java-algorithm-interview