락업 기간이 걸린 사내 주식 매도

문제

사내 우리사주 계좌에서는 주식을 산 뒤 락업(의무 보유) 기간 이 끝나야 팔 수 있습니다. d일짜리 락업이 걸려 있다면, i일에 산 주식은 i + d일 이후(당일 포함)에만 팔 수 있습니다.

일별 종가가 prices 배열로 주어집니다(prices[i]는 i일의 가격). 계좌에서는 매수 1회, 매도 1회 만 할 수 있습니다.

이익이 가장 큰 매매의 [이익, 매수일, 매도일]을 반환하는 solution(prices, d) 함수를 작성하세요. 이익이 0보다 큰 매매가 하나도 없다면 아무것도 사지 않고 [0, -1, -1]을 반환합니다.

이익이 같은 매매가 여럿이면 매도일이 더 빠른 쪽, 그래도 같으면 매수일이 더 빠른 쪽 을 답으로 합니다.

예시

prices=[12,9,14,7,10,18,11], d=2 → [11, 3, 5]
  3일에 7로 사서 5일에 18에 판다(5 - 3 = 2 ≥ d). 이익 11.
 
prices=[5,30,6,9], d=2         → [4, 0, 3]
  0일에 5로 사고 1일에 30에 팔면 이익 25지만 락업이 2일이라 불가능하다.
  가능한 매매 중에서는 0일 매수 → 3일 매도(이익 4)가 최선이다.
 
prices=[20,17,15,12], d=1      → [0, -1, -1]
  어떤 조합도 이익이 0보다 크지 않다.
 
prices=[1,5,1,5], d=1          → [4, 0, 1]
  (0,1)과 (0,3) 모두 이익 4지만 매도일이 빠른 (0,1)을 고른다.

제약 조건

• 1 ≤ prices.length ≤ 100,000
• 0 ≤ prices[i] ≤ 100,000
• 1 ≤ d ≤ 100,000 (d가 prices.length 이상이면 매매 자체가 불가능합니다)
• 매수일 < 매도일이며, 매도일 - 매수일 ≥ d 를 만족해야 합니다

시간 복잡도 목표: O(N)