Week 1-1. [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 

Best Time to Buy and Sell Stock - LeetCode

주어진 주식 가격을 보고 얻을 수 있는 최대 이익(매도가격 - 매수가격)을 구하라. 

• 입력
  • prices | int arrray := 해당 날짜의 주식 가격을 나타내는 배열, | prices | ∈ [1, 10^5]
• 출력
  • k | int := 최대 이익
• 조건
  • | prices[i] | ∈ [0, 10^4]

 

🔎 어떤 식으로 접근했는가?

맨 처음에는 2중 for문을 이용해 하나씩 매수일로 잡고, 매수일 이후를 순회하며 최대 이익을 구했다.

하지만 prices의 최대 길이가 100,000으로 당연하게도 Time Limit Exceeded가 발생했다.

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        for (int i=0; i<prices.length; i++) {
            for (int j=i+1; j<prices.length; j++) {
                if (prices[j] - prices[i] > ans) {
                    ans = prices[j] - prices[i];                
                }
            }
        }
        return ans;
    }
}

 

이후 Two Pointer 방식을 생각했다.

왼쪽에서부터 lp를 이용해 순회하고, 오른쪽에서부터 rp를 이용해 순회하면서 max 값과 min 값을 찾는 것이다.

아래 구현 코드가 그것인데, 결과적으로 테스트 케이스에는 성공했지만 히든 케이스에서 실패했다.

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

prices의 최대 길이가 100,000이므로 반복문은 하나만 사용해야 한다.

 

📝 의사 코드

lp = 0
rp = 맨 마지막 인덱스

mn = 왼쪽부터 최솟값 (매수)
mx = 오른쪽부터 최댓값 (매도)

while (lp <= rp) {
	prices[lp]가 최솟값이라면 최솟값 갱신
    prices[rp]가 최댓값이라면 최댓값 갱신
    lp++
    rp++
}

최솟값이 최댓값보다 크다면 0 반환 (이익을 얻을 수 없는 것)
아니라면 (rp-lp) 반환

 

🎯 구현 코드

아래 코드는 패스하지 못하는 코드이다.

lp++ 과 rp-- 을 하면서 결국 중앙으로 모이는데, 매수액과 매도액이 좌측 혹은 우측에 모여있을 때 테스트 케이스를 통과하지 못한다.

class Solution {
    public int maxProfit(int[] prices) {
        int lp = 0;
        int rp = prices.length-1;

        int mx = -1; // 매도액
        int mn = 1000; // 매수액

        int ans = 0;
        while (lp <= rp) {
            if (prices[lp] < mn) {
                mn = prices[lp];
            }
            if (prices[rp] > mx) {
                mx = prices[rp];
            }
            lp++;
            rp--;
        }

        ans = mx - mn;
        if (ans <= 0) {
            ans = 0;
        }
        return ans;
    }
}

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

통과하지 못한 코드라 성능 측정이 크게 의미는 없지만, while문을 사용하였으므로 시간 복잡도는 O(N)이다.

 

✍️ 성능 회고

N은 최대 100,000이므로 감당할 수 있는 범위이다.

 

보통 1초 제한이라고 할 때, O(N)은 약 1억까지 O(N^2)은 약 1만까지 감당할 수 있다.

따라서 해당 문제를 2중 for문으로 구현한다면 터지게 될 것이다.

 

💡 무엇을/어떻게 개선할 수 있을까?

반복문을 한 번만 사용하면서 최대 이익을 계산할 수 있도록 개선해야 한다.

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

prices를 순회하면서 매수액(mn, 최소 금액) 갱신 & 이익(pist, 매도액 - 매수액)을 계산하여 최대 이익을 구한다.

class Solution {
    public int maxProfit(int[] prices) {
        int mn = Integer.MAX_VALUE; // 매수액 (최소 금액)
        int pist = 0; // profit if sold today: 오늘 팔았을 때 이익
        int ans = 0; // 최종 이익

        for (int i=0; i<prices.length; i++) {
            if (prices[i] < mn) {
                mn = prices[i]; // 매수액 갱신
            }

            // prices[i]를 매도액이라고 가정하고 이익 계산
            pist = prices[i] - mn;

            if (ans < pist) { // 오늘 팔았을 때 이익이 더 크다면 최종 이익 갱신
                ans = pist;
            }
        }
        return ans;
    }
}

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

단일 for문을 사용하여 시간 복잡도는 O(N)이다.

 

느낀 점

단일 for문을 사용하는데 초점을 맞추어 고민하다보니 계속해서 Two Pointer를 사용하는 방식밖에 떠오르지 않았다.

어디선가 풀어본 문제 유형이었는데 끝까지 풀지 못해 아쉬웠다. 기억이 흐려질 때 쯤 꼭 다시 한번 풀어볼 문제이다.