백만 장자 프로젝트

문제 링크 : https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

문제 제목 : 백만 장자 프로젝트

문제 풀이

import java.util.*;

class Solution
{
    public static void main(String args[]) throws Exception
    {
        // Scanner 객체 생성
        Scanner sc = new Scanner(System.in);

        // 테스트 케이스의 개수 입력
        int T = sc.nextInt();

        // 테스트 케이스 수만큼 반복
        for(int i = 1; i <= T; i++) {
            // 배열의 크기 입력
            int N = sc.nextInt();

            // 입력된 크기만큼의 배열 생성
            int[] arr = new int[N];

            // 배열에 요소 입력
            for(int j = 0; j < N; j++) {
                arr[j] = sc.nextInt();      
            }

            // 최대값을 저장할 변수 max, max 이전의 숫자들을 합한 변수 cost, max 이전의 숫자 개수를 저장할 변수 num, 결과값을 저장할 변수 result 초기화
            long max = Long.MIN_VALUE;
            int num = 0;
            long cost = 0L;
            long result = 0L;

            // 배열 뒤에서부터 탐색
            for(int j = arr.length - 1; j >= 0; j--) {
                // 현재 숫자가 최대값보다 큰 경우
                if(arr[j] > max) {
                    // 결과값에 이전 최대값 * 이전 숫자 개수 - 이전 숫자들의 합을 더해줌
                    result += (max * num - cost);
                    // 최대값 갱신
                    max = arr[j];
                    // 비용(cost) 초기화
                    cost = 0;
                    // 숫자 개수(num) 초기화
                    num = 0;
                }
                else {
                    // 최대값이 아닌 경우, 비용(cost)에 현재 숫자 더하고 숫자 개수(num) 증가
                    cost += arr[j];
                    num++;
                }
            }

            // 마지막으로 결과값에 남은 부분 추가
            result += (max * num - cost);

            // 결과 출력
            System.out.println("#" + i + " " + result);
        }
    }
}