[SW Expert 1859] 백만 장자 프로젝트 (JAVA)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=%EB%B0%B1%EB%A7%8C&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

package ssafyjava01;

import java.util.Scanner;

public class SW1859 {
	static int T, N;
	static long sum, max;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		T=sc.nextInt();
		for (int i=1; i<=T; i++) {
			N=sc.nextInt();
			sum=0;
			max=0;
			int[] arr=new int[N];
			for (int j=0; j<N; j++) {
				arr[j]=sc.nextInt();
			}
			for (int j=N-1; j>=0; j--) {
				if (arr[j]>max) {
					max=arr[j];
				}
				else {
					sum+=(max-arr[j]);
				}
			}
			System.out.printf("#%d %d\n",i,sum);
		}
	}

}

꽤나 고민했던 문제..

분명 앞에서부터 탐색하면 지역 최대값이 언제 나오는지 모르므로,

O(N^2) 시간으로 탐색해야 된다..

 

하지만 뒤에서부터 탐색하게 되면 O(N) 으로 가능하다!!

뒤에서 부터 탐색하는 아이디어를 떠올리는게 어려웠던 것 같다..

뒤에서부터 max값을 구한 뒤 탐색할 때 max값이 새로 갱신될때까지(즉 지금 max보다 큰게 나올때까지) 계속해서 값들을 더해주면 된다.((자기 max 값-자기보다 작은 값)들을 계속 더해줌)