Leet Code - 122. Best Time to Buy and Sell Stock II(C++)

예제: Best Time to Buy and Sell Stock II

문제
Say you have an array for which the i'th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

풀이

개인적으로 어려운 문제였다.
Best Time to Buy and Sell Stock과 같은 규칙을 가지고 있으나, 몇 번 거래하는지와는 관계 없이 최대의 이익을 내면 되는 조건이 추가가 되었다.

필자가 생각한 방법은,
1. 최소값(fst)이 갱신되는 지점으로 구간을 각각 나눈다.
2. 그 구간 안에서 최대값을 도출하여, 최대값들의 합을 return한다.
3. 구간 내에서 snd값은, fst와 비슷하지만, res값에 대한 연산이 일어날때마다 그 값이 prices[i]가 된다.
4. res값에 대한 연산이 일어나면(최소값이 갱신되지 않으면) prices[i] - fst, res + prices[i] - snd를 비교하여 더 큰 수를 res에 집어넣는다.

간략하게 위와 같은 로직을 코드로 구현하였다.

전체적인 소스코드는 아래와 같다.

소스 코드

class Solution {
public:
	int maxProfit(vector<int>& prices) {
		int res = 0;
		int sum = 0;

		int size = prices.size();
		if (!size) return res;

		int fst, snd;
		fst = snd = prices[0];

		for (int i = 1; i < size; i++) {
			if (snd > prices[i]) {
				snd = prices[i];
			}

			if (fst > prices[i]) {
				fst = prices[i];
				sum += res;
				res = 0;
			}
			else {
				res = max(prices[i] - fst, res + prices[i] - snd);
				snd = prices[i];
			}
		}
		sum += res;

		return sum;
	}
};

풀이 후기

다른 사람들의 풀이를 보니, 대부분 하나의 for문으로 해결하고 있지만, 필자의 풀이와 비슷하게 한눈에 보기 어려운 코드들이 많았다. 문제 특성상 깔끔하게 풀기 어려운 문제였나보다.
이번 문제를 풀며 내가 생각한 로직들을 종이에 써가면서 풀었는데, 정리도 잘 되고 코드로 구현할 때 실수도 적어지는 느낌이 들었다. 이래서 알고리즘 문제를 풀 때 종이와 펜이 필요한가보다.