Week 1-1. [Array / String] 122. Best Time to Buy and Sell Stock II

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

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

Best Time to Buy and Sell Stock II - LeetCode

주어진 주식 가격을 보고 얻을 수 있는 이익의 총합을 구하라. (기간 내에 여러번 사고 팔 수 있다.)

• 입력
  • nums | int arrray := 정수 배열, | prices | ∈ [1, 3*10^4]
• 출력
  • k | int := 이익의 총합
• 조건
  • | prices[i] | ∈ [0, 10^4]

 

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

이전 Best Time to Buy and Sell Stock 문제와 유사하여 해당 풀이를 떠올렸다.

다른 점은 이전 문제는 한 번만 사고 팔 수 있었고, 지금은 여러번 사고 팔 수 있어 이익의 총 합을 구하는 것이다.

 

따라서 0보다 큰 이익이 발생했다면 이익을 누적해야 하고, 여러번 매수할 수 있도록 매수액을 갱신해야 한다.

 

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

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

 

📝 의사 코드

매수액 = 10000 (큰 값)
최종 이익 = 0
오늘 팔았을 때 이익 = 0

for (0부터, 마지막까지, 1씩 증가) {
	if (prices[i]가 매수액보다 작다면) {
    	매수액을 prices[i]로 갱신
    }
    오늘 팔았을 때 이익 계산 (prices[i] - 매수액)
    if (이익 발생한다면) {
    	최종 이익 += 오늘 팔았을 때 이익
        매수액을 매도액으로 갱신
    }
}

 

🎯 구현 코드

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

        for (int i=0; i<prices.length; i++) {
            if (mn > prices[i]) {
                mn = prices[i];
            }
            pist = prices[i] - mn;
            if (pist > 0) { // 오늘 팔았을 때 이익이 발생한다면
                ans += pist; // 이익 누적
                mn = prices[i]; // ✅ 매수액을 매도액으로 초기화
            }
        }
        return ans;

    }
}

 

내 코드를 탐구해보기

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

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

 

✍️ 성능 회고

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

 

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

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

 

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

히든 케이스까지 통과할 수는 있었지만 만족스럽지는 않은 코드이다.

나중에 다시 보았을 때 어떻게 이런 코드가 나왔는지 곰곰히 생각해 보아야 할 것 같기 때문이다.

 

성능은 나쁘지 않지만 다른 사람이 보았을 때에도 이해하기 쉽도록 더 직관적으로 변경하면 좋을 듯 하다.

 

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

🎯 구현 코드

내 코드보다 직관적인 코드라고 생각한다.

class Solution {
    public int maxProfit(int[] prices) {
        ArrayList<Integer> priceGain = new ArrayList<Integer>();
        
        for(int i=0 ; i<prices.length-1; i++){
            if(prices[i] < prices[i+1]){ // 주식 가격이 증가한다면
                priceGain.add(prices[i+1] - prices[i]); // 이익 추가
            }
        }
        return priceGain.stream().mapToInt(n->n).sum();
    }
}

 

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

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

 

느낀 점

가능하다면, 자신만의 논리보다는 모두가 직관적으로 이해할 수 있는 코드를 짜고 싶다. 물론 실행되는게 우선이긴 하겠지만!