문제
주식 가격이 N일치 주어질 때, 하루에 주식을 1주 사거나, 주식을 팔거나(보유한 주식 전량), 아무것도 하지 않을 수 있다. 최대 이익을 계산한다.
입력
- 첫째 줄: 테스트 케이스 수 T
- 각 테스트 케이스: N (주식 일수), 이어서 N개의 주가
출력
각 테스트 케이스마다 최대 이익을 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 3 1 2 3 5 5 4 3 2 1 | 2 0 |
풀이
배열을 역순으로 순회하며 현재까지 확인한 최대 가격(tmp)을 유지한다. 현재 날의 가격이 tmp보다 크면 새로운 최대가로 갱신하고, 작으면 tmp - arr[i]만큼 이익을 누적한다.
- 배열을 오른쪽 끝(마지막 날)부터 순회한다.
tmp를 현재까지 만난 최대 주가로 관리한다.- 현재 가격이
tmp보다 크면tmp를 현재 가격으로 갱신한다. - 현재 가격이
tmp보다 작거나 같으면ans += tmp - arr[i]로 이익을 더한다. - T개 테스트 케이스를 반복 처리 후 출력한다.
핵심 아이디어: 앞에서부터 탐색하면 미래 최대값을 알 수 없어 탐욕적 선택이 어렵다. 뒤에서부터 순회하면 오른쪽에서 확인된 최대 가격이 현재 날 이후에 팔 수 있는 최선의 가격이 되므로, 해당 가격에 팔 수 있는 모든 날에서 이익을 단번에 수집할 수 있다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day89BOJ11501주식배열역순회 {
static int N;
static long ans; // 1_000_000 * (10_000 - 2) 모든날이 2이고 마지막날 최대값
static int[] arr;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
int T = Integer.parseInt(br.readLine());
while (T-- > 0) {
N = Integer.parseInt(br.readLine());
ans = 0;
arr = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
int tmp = 0;
for (int i = N - 1; i >= 0; i--)
if (arr[i] > tmp)
tmp = arr[i];
else
ans += tmp - arr[i];
sb.append(ans + "\n");
}
System.out.println(sb);
br.close();
}
}
// 팔아야 하는 날을 찾는다. -> 최대값을 갖는 날을 찾는다
// 최대값인 날 전에 있는 값들은 최대값에 팔 수 있지만,
// 최대값 다음 날부터는 다른 두번째 최대값을 찾아야 한다.
// 즉, 뒤에서부터 값을 최대값으로 놓고,
// 나보다 큰 값이 나올때까진 그 값에 팔고, 새로운 큰 값이 나오면
// 그값으로 최대값을 변경한다.
// 어서 풀었던 문제 같은데, 왜 백준 기록에 없지..복잡도
- 시간: O(N) — 배열을 1회 역순 순회
- 공간: O(N) — 주가 배열 저장