주식11501

https://www.acmicpc.net/problem/11501

풀긴했는데 뭔가 시간을 보니 비효율적으로 짯네;;

풀이는 다음과 같다

int 배열로 가격을 받았다
TreeMap 으로 가격을 내림차순으로 만들고 수량도 체크하였다.

배열을 순회하면서

TreeMap 에서 현재가격의 수량을 -1 해주고 0이면 제거한다(현재를 기준으로 가장 비싼 가격을 알기위함)

현재 가격이 TreeMap 의 첫번째 원소의 가격(즉 가장 비싼 가격) 보다 낮으면
1개 구매

현재 가격이 첫번째 원소의 가격(즉 가장 비싼 가격)과 같으면
전부 판매

반례 (내가 만듦)
1
6
5 10 10 20 5 1

ans:35

다른 방법
뒤에서 부터 순회하면서 풀면 훨씬 간단해질것 같네 왜 이생각을 몬했지

import java.io.*;
import java.util.*;
public class Main
{
    static final int MAX = 10000;
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; ++i)
        {
            int N = Integer.parseInt(br.readLine());//1000000
            int[] dayPrice = new int[N];//0~10000
            //PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
            TreeMap<Integer, Integer> prices = new TreeMap<>(Collections.reverseOrder());//가격, 수량. 내림차순
            String[] input = br.readLine().split(" ");
            for(int j = 0; j < N; ++j)
            {
                dayPrice[j] = Integer.parseInt(input[j]);

                if(prices.containsKey(dayPrice[j]))
                    prices.put(dayPrice[j], prices.get(dayPrice[j])+1);
                else
                    prices.put(dayPrice[j], 1);
            }

            int maxPrice = prices.firstKey();

            HashMap<Integer, Integer> stocks = new HashMap<>();//가격, 수량
            Long income = 0L;
            for(int j = 0; j < N; ++j)
            {
                int cur = dayPrice[j];

                if(prices.containsKey(cur))
                {
                    if(prices.get(cur) > 1)
                        prices.put(cur, prices.get(cur)-1);
                    else
                        prices.remove(cur);
                }


                if(cur > 0 &&  cur < maxPrice)//구입
                {
                    if(stocks.containsKey(cur))
                        stocks.put(cur, stocks.get(cur)+1);
                    else
                        stocks.put(cur, 1);
                }
                else if(cur == maxPrice)//가진거 전부 판매
                {
                    for (Integer price : stocks.keySet())
                    {
                        income += (maxPrice - price) * stocks.get(price);
                    }

                    stocks.clear();

                    if(prices.isEmpty() == false)
                        maxPrice = prices.firstKey();

                }

            }

            System.out.println(income);
        }
    }
}