[LeetCode/Top Interview 150] [Array / String] 121. Best Time to Buy and Sell Stock

문제 링크: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: easy

문제:

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

1 <= prices.length <= 105
0 <= prices[i] <= 104

전략:

우선은 가장 간단하고 단순한 해법부터
사는 날과 파는 날의 차이를 이중 for 문으로 구현해서 초기값 0인 max_profit 갱신하면서 찾기 -> 시간초과
최고,최저값의 값과 위치를 기록하며 비교하기

코드 구현:

class Solution {
    public int maxProfit(int[] prices) {
        int max_profit = 0;
        int max = -1;
        int min = Integer.MAX_VALUE;
        int max_pos = 0;
        int min_pos = 0;
        for (int i=0;i<prices.length;i++) {
            int now = prices[i];
            // 최고가 갱신
            if (now > max) {
                max_pos = i;
                max = now;
            }
            // 차익 계산
            max_profit = Math.max(max_profit, max-min);
            // 새로운 최저가 -> 이전 최고가 사용할 의미 없어지므로 초기화
            if (now < min) {
                min_pos = i;
                min = now;
                max_pos = i;
                max = now;
            }
        }
        return max_profit;
    }
}

실행결과:
Time: 2 ms (84.90%), Space: 60.6 MB (85.52%) - LeetHub
https://github.com/1-vL/LeetCode/blob/main/0121-best-time-to-buy-and-sell-stock/0121-best-time-to-buy-and-sell-stock.java

개선 방안:

배열 정렬 후 최소값과 최대값의 차이만큼 나오면 즉시 return 하도록 하면 더 빨라지려나? -> 딱히 성능에 도움이 되지는 않을듯...
사용 안 하는 pos 변수들 제거

class Solution {
    public int maxProfit(int[] prices) {
        int max_profit = 0;
        int max = -1;
        int min = Integer.MAX_VALUE;
        
        for (int i=0;i<prices.length;i++) {
            int now = prices[i];
            
            // 최고가 갱신
            if (now > max) {
                max = now;
            }
            
            // 차익 계산
            max_profit = Math.max(max_profit, max-min);
            
            // 새로운 최저가 -> 이전 최고가 사용할 의미 없어지므로 초기화
            if (now < min) {
                min = now;
                max = now;
            }
        }
        return max_profit;
    }
}
Accepted	1 ms	61.1 MB	java
// 오차 범위 내인것 같긴 하지만 leetCode 사이트의 테스트 케이스 대상으로는 조금 더 빨라졌다.

Discuss 탭의 타인 코드:

class Solution {
    public int maxProfit(int[] prices) {
        int lsf = Integer.MAX_VALUE; // least so far
        int op = 0; // overall profit
        int pist = 0; // profit if sold today
        
        for(int i = 0; i < prices.length; i++){
            if(prices[i] < lsf){ // if we found new buy value which is more smaller then previous one
                lsf = prices[i]; // update our least so far
            }
            pist = prices[i] - lsf; // calculating profit if sold today by, Buy - sell
            if(op < pist){ // if pist is more then our previous overall profit
                op = pist; // update overall profit
            }
        }
        return op; // return op 
    }
}

// 거의 동일하지만 이익을 비교하는 방식이 조금 다른 것 같다.
// 성능도 오차범위 내에서 동일한 듯
	Accepted	2 ms	61 MB	java

회고:
이 문제 같은 경우 leetCode 사이트의 트래픽에 따라 실행 결과 시간과 메모리 사용량 순위가 결정되는 수준인 것 같아서 너무 신경쓰지 말아야겠다.