1859 백만 장자 프로젝트

백만 장자 프로젝트 URL

내 풀이

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

public class SWEA1859 {

    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());
            Map<Integer, Integer> map = new HashMap<>(); //map 생성
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j < n; j++) {
                int value = Integer.parseInt(st.nextToken());
                map.put(j, value);
            }
            List<Integer> list = new ArrayList<>(map.values());

            list.sort((o1, o2) -> o2 - o1);
            System.out.println(list);
            
        }
    }
}

Solution

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

public class SWEA1859 {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); //테스트 케이스
        
        for (int t = 1; t <= T; t++) {
            int N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int[] day = new int[N];

            for (int i = 0; i < N; i++) {
                day[i] = Integer.parseInt(st.nextToken());
            }
            //System.out.println(Arrays.toString(day));
            long price = 0;
            //뒤에서부터 --> 최대값 - 오늘가격
            int max = 0;
            for (int j = N-1; j >= 0; j--) {
                int today = day[j];
                if (max > today) {
                    price += max - today;
                } else {
                    max = today;
                }
            }
            System.out.printf("#%d " + price, t);
            System.out.println();
        }
    }
}

※ N은 최대 백만이고 매매가 최대는 만으로 price값이 천억이 나올 수 있기 때문에 price는 long으로 선언

1. 뒤에서 부터 체크한다
2. max보다 작으면 무조건 산다
3. 더 큰 지점 발견하면 max 교체

배운점

접근 자체를 잘못했다. 난 Map함수를 이용해 매매가를 기준으로 내림차순 정렬하고 날짜가 큰 수가 나타날 때 까지 1씩 더해주고 마지막 날이면 종료하고 예외처리로 첫 번째 날이 가장 큰 경우 0을 반환하게 하려했다. 결론은 Map정렬까지 했고 value가져오는 것도 해내지 못했다. 이 문제와 별개로 Map에 대해 공부할 필요가 있을것같다.