백준 - 11501 주식(Java)

그리디 문제입니다.

 

문제 조건에 의해 각 주식들은 가장 비싼 날에 팔아야 합니다.

즉, 가격으로 내림차순으로 정렬하여 비싼 주식의 이전 주식들을 계산해서 팔면 됩니다.

 

[구현 코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz;

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

        while (testCase-- > 0){
            int day = Integer.parseInt(br.readLine());
            stz = new StringTokenizer(br.readLine(), " ");
            List<Node> list = new ArrayList<>();
            int[] arr = new int[day];


            for(int i=0; i<day; i++){
                int price = Integer.parseInt(stz.nextToken());
                arr[i] = price;
                list.add(new Node(price, i));
            }

            // 가격 순으로 내림차순 정렬
            list.sort(Node::compareTo);

            long sum = 0L;
            int pre = 0;
            // 비싼 주식부터 순회
            for (Node node : list) {
                // 아직 계산되지 않은 주식일 경우, 해당 계산 범위를 계산함
                if(pre < node.lo){
                    for(int i = pre; i<node.lo; i++){
                        sum += (node.price - arr[i]);
                    }
                }
                pre = Math.max(pre, node.lo + 1);
            }

            bw.write(sum + System.lineSeparator());
        }

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

    private static class Node implements Comparable<Node>{
        int price, lo;

        public Node(int price, int lo) {
            this.price = price;
            this.lo = lo;
        }

        @Override
        public int compareTo(Node o) {
            if(this.price == o.price){
                return o.lo - this.lo;
            }
            return o.price - this.price;
        }
    }
}