[SWEA] 1859

풀이 방식

• 비싼 매매가가 뒤로 나와야한다.
• 비싼 매매가가 중간에 나오면, 그때까지 금액을 계산하고 뒤에서 또 비싼 매매가를 찾아야 한다.
• 즉 매매가 목록을 뒤에서부터 조회하면서, 가장 큰 값을 기록하고, 더 비싼 값이 나오면 그걸 기록하고 그 전까지 판매를 진행한다.
• stack을 사용했는데, 너무 어렵게 풀려고 하는듯

import java.util.*;
import java.io.*;

public class Main {
    static Stack<Integer> stack; // 가격 기록 stack

    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());
        int n;
        StringTokenizer st;

        stack = new Stack<>();

        for(int i=0; i<t; i++) {
            n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<n; j++) {
                stack.add(Integer.parseInt(st.nextToken()));
            }
            bw.write("#"+(i+1)+" "+solution(n)+"\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    // 최대 매매가 구하는 로직
    public static long solution(int n) {
        long answer = 0; // 최종 가격
        long curPrice = 0; // 현재 구매 가격 합
        int max = 0; // 최댓값
        int count = 0;

        for(int i=0; i<n; i++) { // n대신 stack.size() 사용하면 stack은 가변이라서 문제 발생 size()는 while 쓰기
            int cur = stack.pop();
            if(cur > max) { // 새로운 최대값이 나오면 -> 이전까지 구매 정산
                answer = answer + ((long) max *count - curPrice); // 이전까지의 가격 반영
                max = cur; // 최대값 갱신
                count = 0; // 구매 개수 초기화
                curPrice = 0; // 구매 가격 합 초기화
            } else { // 매매하기
                curPrice += cur; // 현재 구매 가격 더하기
                count ++; // 구매 개수 1 증가
            }
        }
        // 마지막 매매 정산 (최대 값이 더 갱신 안 되는 경우)
        answer = answer + ((long) max *count - curPrice);

        return answer;
    }

}