오늘부터 틈날 때 마다 자바 Leetcode 준비를 하나씩 해나가려 한다. 그리고 leetcode 공부에 들어가기에 앞서서 뭐랄까... 마음가짐의 차원이라고나 할까? 그런 의미에서 아래와 같이 고찰 및 마음 정리를 했다.
누군가에게는 뻔한 소리로 들릴 수도 있고, 또 누군가에게는 그저 공허한 외침으로 보일 수도 있겠지만, 어디까지나 내 블로그 포스팅의 제 1 독자는 나이기에 그것만으로도 충분한 의미와 가치가 있다고 생각한다.
Leetcode는 Blind150을 기준으로 분류된 카테고리 별로 돌아가면서 풀어나갈 예정이다. 같은 카테고리를 쭉 이어서, 몰아서 푸는 방식이 나을지 아니면 계속 카테고리를 바꿔가면서 푸는 것이 좋을 지에 대해서는 아직 확신이 서지 않는다. 그런고로 우선은 정해진 카테고리를 최대한 빨리 풀어내고, 다음 카테고리로 넘어가는 방식을 택했다. 그래야 비슷한 유형들을 집중력있게 쭉쭉 나갈 수 있지 않을까 하기 때문이다.
// 121. Best Time to Buy and Sell Stock
//
// 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.
package SlidingWindow;
class BestTime {
public static void main(String[] args) {
int[] arr = { 7, 1, 5, 3, 6, 4 };
System.out.println(maxProfit(arr));
}
public static int maxProfit(int[] prices) {
// This is sliding window type problem.
// Set the left pointer as zero and right pointer as one for initial value.
// Prepare maxProfit to store the maximum profit.
int leftPointer = 0;
int rightPointer = 1;
int maxProfit = 0;
// Move forward the right pointer to the end of prices array.
while (rightPointer < prices.length) {
// Compare the value of left pointer with the value of right pointer.
// If the value of left pointer is smaller than or equal to the right pointer,
// save the difference value into the maxProfit and move forward the right
// pointer.
if (prices[leftPointer] <= prices[rightPointer]) {
// Maintain the maxProfit as maximum value when it has to be updated.
maxProfit = Math.max(maxProfit, prices[rightPointer] - prices[leftPointer]);
rightPointer++;
// If the value of left pointer is larger than the right pointer,
// stick the leftpointer to the right pointer, after that move forward the right
// pointer without any action.
} else {
leftPointer = rightPointer;
rightPointer++;
}
}
return maxProfit;
}
// Time complexity is O(N) where N is the length of array
// Space complexity is O(1)
}
문제를 풀 때는 가급적이면 최대한 자세하게 comment를 달아서 다음에 다시 보게 되더라도 보다 빠르게 이해를 할 수 있도록 하였다. 그래서 포스팅의 본문에는 핵심 로직만 정리하고, 나머지는 comment를 다시 봄으로써 리뷰를 가능하도록 셋팅했다.
로직의 흐름은 비교적 단순하다. left pointer와 right pointer를 두고, 또 max profit을 저장할 value를 하나 셋팅한 다음에 상황과 조건에 따라서 이 pointer들을 이동시켜 가면서 max profit을 산출해 내는 방식이다.
핵심은 어떤 조건과 상황을 설정해서 윈도우를 움직일 것이냐 이다.
물론 이 문제도 지난 방학 때, 한차례 풀어봤었지만 역시나 기억이 잘 나지 않아서 다시 모범 답안을 본 케이스이다. 하지만 분명한 사실은 그때 봤던 코드 대비, 지금 다시 보니 이해의 폭과 깊이가 더 늘어났다는 점이다.
반복적으로 복습의 주기를 어떻게 잡느냐에 대해서는 아직 명확한 답을 내지 못했다. 일주일 단위로 볼 것인지, 이주일 단위 아니면 한달 단위로 볼 것인지에 대해서는 차차 진행을 해 가면서 결정해야 하겠다.
댓글 없음:
댓글 쓰기