[Day2] Best Time to Buy and Sell Stock

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

Best Time to Buy and Sell Stock - LeetCode

 

 

<문제 설명>

prices 배열이 있다. 각 인덱스 i는 day고 각 날의 stock 가격이 prices[i]를 의미한다. 이익을 최대화하기 위해 한 날짜를 선택하고 하나의 stock을 산다. 그리고 다른 미래의 날짜를 선택하고 stock을 판다. 이 거래에서의 최대 이익을 return 하고 이익이 없으면 0을 return한다.

 

 

<풀이 과정>

1. 첫 번째로 생각한 방법은 배열을 끝까지 돌면서 제일 작은 수를 찾는다. 그 다음 날짜들 중 작은 수와의 gap을 찾아서 제일 큰 gap이 나오는 값을 return하도록 코드를 작성하였다. 하지만 이 코드의 문제는 배열에서 제일 작은 수를 찾는 것이다. 왜냐하면 제일 작은 수를 찾았음에도 불구하고 그 제일 작은 수 이전에 이익을 최대화 할 수 있는 다른 방안이 있다면 이 코드로 정확한 결과를 찾을 수 없다. 

 

2. Leetcode에서 힌트로 준 Dynamic Programming(동적계획법)을 사용했다. DP는 큰 문제를 작은 문제로 나누어 푸는 문제로 작은 부분 문제들이 반복되는 것을 이용해 풀어나가는 방법이다. 이때, 모든 작은 문제들을 한번만 풀어야 한다. 따라서 정답을 구한 작은 문제를 어딘가에 메모해놓아 저장한다. 왜냐하면 작은 문제의 답은 변하지 않기 때문에 다시 그 보다 큰 문제를 풀어나갈 때, 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과 값을 이용한다. 이 부분이 분할 정복과 다른 점이다. 내가 생각하기에 DP는 너무나 모호한 알고리즘이어서 관련문제를 더 풀어보며 이해를 해나가야겠다. 

 

 

<풀이 코드>

2.

class Solution {
    public int maxProfit(int[] prices) {
        int min = 10000;
        int between = 0;
        int gap = 0;
        
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
            }
            gap = prices[i] - min;
            if(between < gap) {
                between = gap;
            }
        }
        return between;
    }
}

 

 

<참고한 블로그>

https://galid1.tistory.com/507