[SWEA 1859번 /JAVA] 백만 장자 프로젝트

Question

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc 

SW Expert Academy

 

---

💡 Solution

가장 먼저 든 생각은 배열에서 최댓값을 찾아 '최댓값 - 그 전에 있는 값'을 누적하여 결과를 도출하려 했습니다.

이때 뒤에서부터 최댓값을 찾으면 더 효율적으로 답을 찾을 수 있습니다.

 

이때 조심해야할 부분은 N의 최댓값 1,000,000(10^6)이고 각각의 매매가의 최댓값은 10,000(10^4)이므로, 만일 N이 10^6이고 모든 날의 매매가가 10^4이라면 결괏값은 최대 10^10이 나옵니다. int형은 대략 10^3까지 지원하므로 결괏값이 될 profit을 long형으로 선언해줍니다.

 

💻 Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


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());
            long profit = 0;
            int max = 0;
            int[] price = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            for(int j = 0; j < N; j ++) {
                price[j] = Integer.parseInt(st.nextToken());
            }

            for(int j = N - 1; j >= 0; j--) {
                if(price[j] > max) {
                    max = price[j];
                }
                profit += max - price[j];

            }
            System.out.printf("#%d %d\n", i + 1, profit);

        }

    }
}