[SW Expert Academy] 백만 장자 프로젝트 (D3)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1

SW Expert Academy

 

import java.util.Scanner;

class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();

		for (int tc = 1; tc <= t; tc++) {
			int n = sc.nextInt();

			int arr[] = new int[n];

			for (int i = 0; i < n; i++) {
				arr[i] = sc.nextInt();
			}

			int max = Integer.MIN_VALUE;
			long sum = 0;

			for (int i = arr.length - 1; i >= 0; i--) {
				if (max < arr[i])
					max = arr[i];

				sum += max - arr[i];
				
				//System.out.println(sum);
			}
			System.out.println("#" + tc + " " + sum);
		}

	}
}

처음에는 큐를 사용했으나 계속해서 큐를 보는 것은 N이 최대 10^6이어서 시간 초과가 발생했다.

배열을 뒤에서부터 살펴보는 것이 정답이다.

 

sum은 자연수의 개수가 10^6, 매매가가 최대 하루에 10^4이어서 int범위를 초과한다.

따라서 long으로 작성해주어야 한다.