#121 Best Time to Buy and Sell Stock

문제링크 - https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150

문제 분석

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4
  주어진 배열에서 가장 싸게 팔고 가장 비싸게 팔아야 한다.
  사는것은 파는것 보다 앞에 있어야 한다.

문제 해결

문제 해결 로직

사는것이 파는것 보다 앞에 있어야 한다는 것 때문에 쉬운 문제임에도 투포인터로 삽질을 좀 했다.

1. 매수할 날짜를 0으로 선언하고, 매도할 날짜를 1 끝으로 옮기며 탐색한다.
2. 매도 가격과 매수 가격을 비교한다.
   2-1. 매도 가격이 크면 최대 값과 비교하여 교체한다.
   2-2. 만약 매수 가격보다 작으면 매수 날짜를 매도할 날짜로 변경한다.

코드 작성

class Solution {
    public int maxProfit(int[] prices) {

        int maxValue = 0;
        int buyIndex = 0; // 매수할 날짜를 가리키는 포인터

        for (int sellIndex = 1; sellIndex < prices.length; sellIndex++) {
            if (prices[sellIndex] > prices[buyIndex]) {
                // 현재 날짜에 매도하여 이익을 얻을 수 있는 경우
                maxValue = Math.max(maxValue, prices[sellIndex] - prices[buyIndex]);
            } else {
                // 현재 날짜에 매수할 수 있는 경우
                buyIndex = sellIndex;
            }
        }

        return maxValue;
    }
}

회고

• 투포인터로 문제를 풀기엔 수를 오름차순으로 정렬할 수 없었으며 예외 케이스가 생기는 경우가 있었다. ex. [2,1,2,0,1]

        // int startIndex = 0;
        // int endIndex = prices.length-1;
        // int maxValue = 0;

        // while(startIndex < endIndex){
        //   if(prices[startIndex]>=prices[startIndex+1]){
        //     startIndex++;
        //   }else if(prices[endIndex]<=prices[endIndex-1]){
        //     endIndex--;
        //   }else{
        //     maxValue = Math.max(maxValue, prices[endIndex] - prices[startIndex]);
        //     startIndex++;
        //     endIndex--;