https://www.acmicpc.net/problem/11501
11501번: 주식
입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타
www.acmicpc.net
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
int[] stock_price = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
stock_price[j] = Integer.parseInt(st.nextToken());
}
long answer = 0;
int max_stock_price = 0;
for (int index = N - 1; index >= 0; index--) {
if (max_stock_price < stock_price[index]) {
max_stock_price = stock_price[index];
} else {
answer = answer + (max_stock_price - stock_price[index]);
}
}
bw.write(answer + "\n");
}
bw.flush();
bw.close();
}
}가장 비싼 날을 찾아서 그 앞날을 전부 판매
그 뒤 인덱스부터 또 비싼 날을 찾아서
그 앞날을 전부 판매 반복
그냥 뒤에서부터 max 갱신하며 팔아치우기
O(N)