[SWEA / Java] 1859. 백만 장자 프로젝트

💡 Info

• 난이도: D2
• 시간 제한: 10개의 테스트 케이스를 합쳐서 30초
• 메모리 제한: 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내
  SWEA 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc
  풀이 링크(GitHub): hayannn/CodingTest_Java/SWEA/D2/1859. 백만 장자 프로젝트

💭 문제 이해

• 조건을 벗어나지 않는 한의 최대한의 사재기 이득을 구하기

📥입력 조건

• 첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
• 각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,
• 둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.
• 각 날의 매매가는 10,000이하이다.

3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

📤출력 조건

• 각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.

#1 0
#2 10
#3 5

💭 생각한 알고리즘

실제 풀이 시간 : 1시간 42분

• 매일의 주가가 주어졌을 때, 각 날짜마다 이후의 최대 주가를 찾아 그 차이 구하기
• 이후의 최대 주가와의 차이를 모두 더하여 투자자가 얻을 수 있는 총 이익을 계산

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.List;
import java.io.FileInputStream;

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

		for(int test_case = 1; test_case <= T; test_case++)
		{
			int n = Integer.parseInt(sc.nextLine());
			List<Integer> numList = Arrays.stream(sc.nextLine().split(" "))
					.map(Integer::parseInt)
					.collect(Collectors.toList());
			
			int[] temp = new int[numList.size()];
			int max = 0;
			double result = 0;
			
			for(int i=n-1; i>=0; i--) {
				if(max < numList.get(i).intValue())
					max = numList.get(i).intValue();
					temp[i] = max - numList.get(i).intValue();
			}
			for(int i=0; i<temp.length; i++)
				result += temp[i];
			 System.out.println("#" + test_case + " " + Math.round(result));
		}
	}
}