Best Time to Buy and Sell Stock III - LeetCode

Problem

1. input: 날짜별 주식의 가격이 담긴 리스트 prices
2. output: 주식을 두번 사고 팔 때, 얻을 수 있는 최대 수익 리턴
3. 주식은 하나를 사고 판매한 후에, 다른 주식을 살 수 있음
4. 같은 날 주식을 팔고 살 수 없음
   • 1 <= prices.length <= 10^5
   • 0 <= prices[i] <= 10^5

Idea

주식을 동시에 두개 갖고 있을 수 없고, 같은 날 팔고 살 수 없기 때문에 2번의 구매, 판매는 아래와 같이 이루어 진다.

특정 날짜를 기준으로 앞뒤로 구간이 나누어지고, 각 구간에서 최소값에 구매, 최대값에 판매를 할 때, 수익이 최대가 된다. 즉, 최대 수익을 찾는 과정은 2단계이다.

1. 구간을 나눌 기준 정하기 → 첫번째 주식 판매의 최대치
2. 나눠진 앞,뒤 구간에서 가격의 최대값, 최소값 찾기

위의 아이디어 단순 for문으로 완전 탐색을 하면 O(n^2)으로 시간 초과가 난다 → Sol1

시간 초과를 피하기 위해 Sol1의 풀이에서 n^2을 n으로 바꿔야 한다. 결국 첫번째 주식은 아무리 늦게 팔아도 구간을 나누는 기준선을 넘을 수 없고, 두번째 주식은 아무리 빨리 살려고 해도 기준선보다 빠를 수 없다. 때문에 진행 방향에 따른 최댓값, 최솟값 찾기로 이중 for문으로 찾던 각 구간별 최대 수익을 for문으로 구할 수 있다 → Sol2

Solution

1. 완전탐색

   1. 각 날짜를 판매일로 둘 때, 주식 판매의 최대수익 구하기
   2. 각 날짜를 구매일로 둘 때, 주식 판매의 최대수익 구하기
   3. 전체 수익을 최대로 하는 기준선 찾기

   class Solution {
       fun maxProfit(prices: IntArray): Int {
           val n = prices.size
           val firstMax = Array<Int>(prices.size) { 0 }
           val secondMax = Array<Int>(prices.size) { 0 }
   				// 각 날짜를 판매일로 둘 때, 첫번째 주식 판매의 최대수익 구하기
           for (buy in 0 until n - 1) {
               for (sell in buy + 1 until n) {
                   firstMax[sell] = listOf(firstMax[sell-1],firstMax[sell],prices[sell] - prices[buy]).max()!!
               }
           }
   				// 각 날짜를 구매일로 둘 때, 두번째 주식 판매의 최대수익 구하기
           for (buy in n - 2 downTo 0) {
               for (sell in n - 1 downTo buy + 1) {
                   secondMax[buy] = listOf(secondMax[buy], secondMax[buy + 1], prices[sell] - prices[buy]).max()!!
               }
           }
   				// 전체 수익을 최대로 하는 기준선 찾기
           var max = 0
           for (i in prices.indices) {
               max = maxOf(max, firstMax[i]+secondMax[i])
           }
           return max
       }
   }
   

   시간 복잡도: 배열 순회 X 배열 순회 + 배열 순회 = n^2

   

2. 진행방향에 따른 최대,최소값 구하기

   ex) 첫번째 주식 판매의 최대 수익 구하기

   • 0~1, 0~2, … 0~n 각 구간별 최소값 찾기
   • 0~1, 0~2, … 0~n 각 구간별 최대값 찾기
   • 기준선이 주어졌을 때, 해당 기준선을 최대 범위로 하는 최소,최대값으로 최대 수익을 구할 수 있다.

   ⇒ 이중 for문이 for문 2개로 분리할 수 있음

   class Solution {
       fun maxProfit(prices: IntArray): Int {
           val n = prices.size
           val leftMin = Array<Int>(prices.size) { prices[0] }
           val rightMax = Array<Int>(prices.size) { prices[n-1] }
   				// 좌->우 최소값
           for (i in 1 until n) {
               leftMin[i] = minOf(leftMin[i - 1], prices[i])
           }
   				// 우->좌 최대값
           for (i in n-2 downTo 0) {
               rightMax[i] = maxOf(rightMax[i + 1], prices[i])
           }
           val firstMax = Array<Int>(prices.size) { 0 }
           val secondMax = Array<Int>(prices.size) { 0 }
   				// 첫번째 구간 최대 수익 구하기
           for (sell in 1 until n) {
               firstMax[sell] = listOf(firstMax[sell-1],firstMax[sell],prices[sell] - leftMin[sell]).max()!!
           }
   				// 두번째 구간 최대 수익 구하기
           for (buy in n - 2 downTo 0) {
               secondMax[buy] = listOf(secondMax[buy], secondMax[buy + 1],rightMax[buy] - prices[buy]).max()!!
           }
   				// 전체 수익을 최대로 하는 기준선 찾기
           var max = 0
           for (i in prices.indices) {
               max = maxOf(max, firstMax[i]+secondMax[i])
           }
           return max
       }
   }
   

   시간 복잡도: 배열 순회 + 배열 순회 + 배열 순회 = n

   

Point