결혼을 해야할 때가 되어서, 돈을 좀더 모으고자 주식에 관심을 가지게 된 광성(3x세 미혼)은 어떻게 하면 가장 주식을 성공적으로 거래할 수 있는지를 고민하고 있습니다. 하지만 회사업무와 고양이를 돌보느라 바쁜 광성은 하루에 한번만 거래를 (한번 사고/ 한번 팜) 하기로 결정을 했습니다. 시간순으로 주가가 주어졌을때, 최대 한번씩 사고 / 팔 때 얻을 수 있는 가장 큰 이득이 얼마인지를 알려주세요. (이득을 낼 수 없으면 거래를 하지 않아도 됩니다)
시간제한 1초에 N의 범위가 10,000이니 약 O(N^2)이내의 시간안에 해결 해야 합니다.
아이디어
주가를 각 그래프로보면 [2000, 2050, 3420, 4000, 3000, 1000, 1050, 2000, 1000]
파란색 점 기준으로 각각의 min, max point를 알 수 있습니다. 이때 1번째의 min포인트보다 아래로 떨어지는 경우가 발생하면 min포인트는 갱신되며 떨어지기 이전의 주가는 그것이 최대로 고정됩니다. 그리고 또 반복합니다. 첫 기준은 2000이 min point이며 arr[i]가 증가하면서 max point를 갱신하고 만약 arr[i]가 min point보다 작을경우 그 시점이 첫 번째의 최대 주가(결과)의 이득량입니다. 또 작아진 min point를 갱신하며 또 수행합니다.
즉, O(N)의 탐색으로 결과를 알 수 있습니다.
4. 풀이 방법
맨 첫 데이터를 min_value이자 max_value로 넣어둔다.
현재의 data가 min value보다 작으면 min value를 갱신하고 max value로 갱신한다 (초기화 과정)
현재의 data가 max value보다 크면 max value를 갱신한다.
max value - min value (1분기 최대 이익)가 result (과거 분기 최대 이익)보다 크면 result를 갱신합니다.
댓글