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

문제

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

SW Expert Academy

 

풀이

입력이 너무 많아 테스트가 힘들었던 문제이다.

 

1,000,000일은 약 2738년이라는데......

 

구현은 간단하다. 입력받은 값을 배열로 저장한 후, stream함수를 사용해 최대값을 구했다.

 

루프를 돌며 max값이 나오기 전까지의 합과 개수를 구하고,

 

max를 발견하면 (max * count) - (이전까지의 sum)으로 이익을 구하면 된다.

 

배열을 다시 짤라 다음 max 값을 구하고 똑같은 연산을 수행하면 된다.

 

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

public class 백만장자프로젝트 {
	static int N;
	static int arr[];
	static int max, count, sum, sell;
	static long profit;
	static int tmpArr[];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			
			arr = new int[N];
			
			for (int i = 0; i < N; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			
			max = Arrays.stream(arr).max().getAsInt();
			profit = 0;
			
			for (int i = 0; i < N; i++) {
				count = 0;
				sum = 0;
				sell = 0;
				while(arr[i] != max) {
					sum += arr[i];
					count++;
					i++;
				}
				
				sell = arr[i] * count;
				profit += sell - sum;

				if (i + 1 < arr.length) {
					tmpArr = Arrays.copyOfRange(arr, i + 1, arr.length);
					max = Arrays.stream(tmpArr).max().getAsInt();
				}
			}
			sb.append("#").append(tc).append(" ").append(profit).append("\n");
		}
		
		System.out.println(sb);
	}
}