백준 11501번 주식

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int k = Integer.parseInt(br.readLine());

        for (int i = 0; i < k; i++) {
            ArrayDeque<Integer> stocks = new ArrayDeque<>();
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j < n; j++) {
                Integer stock = Integer.parseInt(st.nextToken());
                stocks.add(stock);
            }

            int maxNum = Integer.MIN_VALUE;
            long total = 0;

            while(!stocks.isEmpty()) {
                int now = stocks.removeLast();

                if (maxNum < now) {
                    maxNum = now;
                    continue;
                }
                total += maxNum - now;
            }
            sb.append(total);
            sb.append("\n");
        }
        System.out.print(sb);
    }
}

주목할 점
1. 주식을 하나밖에 못 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안한다.

하루에 할 수 있는 action은 한 개 이고, 주식은 무조건 하루에 하나 밖에 사지 못한다.
우리는 미래의 주식 가격을 아니까, 미래부터 과거로 순회하면서 O(n)으로 풀이를 진행할 수 있다.

하루에 주식을 하나밖에 못사니까, 미래의 최대 가격보다 낮으면 사서 차곡 차곡 수익을 만드는 것이 이득이다.

우리가 해야될 것은,
1. 미래의 최대가격을 갱신
2. 미래 가격보다 저렴하다면 수익실현

이 두가지만 코드로 구현해내면 된다.

• 못풀었던 이유
  아이디어 부족.. 최대값을 도출

• 출처
  백준 11501

• 비슷한 문제
  프로그래머스 주식가격