[JAVA][LeetCode][SlidingWindow] #121. Best Time to Buy and Sell Stock

문제 / 예시 / 제한조건 :

(정답은 맨 아래)

지금까지 슬라이딩 윈도우 문제 풀었을 때는 left, right 로 양 끝에 인덱스 두고 하는 것만 했었어서,

생각이 그 안에 갇혀있었다.

 

그래서 진짜..

삽질을 많이 한 느낌!

 

나의 삽질.. 

 

실패 :

TRY #1 (94 / 212 testcases passed)

맨 앞을 buyTime으로 설정하고, 맨 뒤를 sellTime으로 설정해서 접근

앞서 말한 것과 같이... 생각이 진짜 갇혀있었음

int maxProfit = 0;
int buyTime = 0, sellTime = prices.length - 1;

while(sellTime > buyTime ) {
    int currentProfit = prices[sellTime] - prices[buyTime];
    currentProfit = Math.max(currentProfit, 0);

    if(currentProfit > maxProfit) {
        maxProfit = currentProfit;
    }

    // move
    int moveCase1 = prices[sellTime] - prices[buyTime + 1];
    int moveCase2 = prices[sellTime-1] - prices[buyTime];

    if(moveCase1 >= moveCase2) {
        ++buyTime;
    } else {
        --sellTime;
    }
}

return maxProfit;

* fail testcase :

prices = [1,2,11,4,7]

Output 9 / Expected 10

 

#2 (174 / 212 testcases passed)

이번에는 그래서 정렬을 먼저 하고, 

정렬된 Array 에서 가장 작은 수 (왼쪽) / 가장 큰수 (오른쪽) 을 투 포인트로 두고 찾는 방식으로 해보자고 생각.

중복되는 경우가 있어서 인덱스를 찾는 것을 넣어줘야 하는 것이 부울편했음.

// Array copy
int[] sortedPrices = new int[prices.length];
System.arraycopy(prices, 0, sortedPrices, 0, prices.length);

// sort
Arrays.sort(sortedPrices);

// check profit
int leftIndex = 0, rightIndex = prices.length - 1;
int buyTime=0, sellTime = 0;
while(leftIndex < rightIndex) {
    // find buyTime from prices.
    for(int i=0; i<sortedPrices.length; i++) {
        if(prices[i] == sortedPrices[leftIndex]) {
            buyTime = i;
            break;
        }
    }

    for(int i=sortedPrices.length-1; i>=0; i--) {
        if(prices[i] == sortedPrices[rightIndex]) {
            sellTime = i;
            break;
        }
    }

    if(sellTime > buyTime) return prices[sellTime] - prices[buyTime];

    if(sortedPrices[rightIndex-1] - sortedPrices[leftIndex]
            > sortedPrices[rightIndex] - sortedPrices[leftIndex+1]) {
        --rightIndex;
    } else {
        ++leftIndex;
    }
}

return 0;

* fail testcase :

Input prices = [4,1,2]

Output 0 / Expected 1

 

#3. (200 / 212 testcases passed)

다 생각해보는 경우

int maxProfit = 0;
for(int i=0; i<prices.length-1; i++) {
    int max = 0, currentProfit = 0;

    for(int j=i+1; j<prices.length; j++) {
        if(prices[j] > prices[i]
                && prices[j] > max) {
            max = prices[j];
        }
    }

    currentProfit = max - prices[i];
    if(maxProfit < currentProfit) {
        maxProfit = currentProfit;
    }
}


return maxProfit;

 

이거는 당연히 타임리밋 걸려버림

알면서도 너무 답답해서 해봄..

 

---

 

그래서 계에속 생각하다가 답을 못찾겠어서 유튜브의 도움

https://youtu.be/1pkOgXD63yU?si=EczX9gv6MRzPsq7E

 

이것도 접근 방법만 보고 바로 풀어보기 시작

 

아니 근데 ..

양 옆으로 포인트를 두는 것도 가능하잖아!?

이런 생각을 못했다니 (´༎ຶོρ༎ຶོ`)

 

멍충멍충~

겨얼국 정답은 ?

int maxProfit = 0;
int buyTime = 0, sellTime = buyTime+1;
while(sellTime < prices.length) {
    if(prices[sellTime] < prices[buyTime]) {
        // set buyTime to sellTime.
        buyTime = sellTime;
    } else {
        // check current profit and maxProfit.
        int currentProfit = prices[sellTime] - prices[buyTime];
        if (currentProfit > maxProfit) {
            maxProfit = currentProfit;
        }
    }

    sellTime ++;
}

return maxProfit;

• Time Complexity: O(n)
• Space Complexity: O(1)

 

 

더 간단하게 하면,

int buyPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
    if (prices[i] < buyPrice) {
        buyPrice = prices[i];
    } else if (prices[i] - buyPrice > maxProfit) {
        maxProfit = prices[i] - buyPrice;
    }
}
return maxProfit;

이렇게나 간단했다니 !!!!!!!!!!!!!!!