[D2-JAVA] SWEA - 백만장자 프로젝트

SW Expert Academy

 

✅ 문제 요약

물건을 팔았을 때의 최대 이익 구하기

 

🤔 문제 접근

처음 문제를 봤을 때는

각 매매가를 우선순위 큐에 내림차순으로 저장하고 매매가의 앞에서부터 진행하여

만약 최대값(큐.poll() 한 값) 에 도달하면 (최대값 전의 매매가격 수 * 최대값) - (최대값 이전의 매매가격 누적합) 

을 통해 문제를 풀고자 했다.

매매가 배열에서 인덱스가 최대값에 도달했다면 다시금 큐에서 poll하여 위 과정을 반복하도록 했지만

푸는 것에 실패했다.

 

더욱 간단한 방법이 있었으니, 매매가 배열의 뒤에서부터 시작하여 만약 현재 매매가가 max매매가보다

작다면 sum에 더해주고 max매매가 보다 현재 매매가가 크다면 max를 현재 매매가로 갱신해주는 방법이다.

 

이와 비슷한 다른 문제에서도 정방향 탐색을 진행하여 복잡하고 어렵게 푸는 문제들이 더러 있었는데

꼭 정방향이 아닌 문제가 풀리지 않는다면 거꾸로 역방향으로도 생각해보는 습관을 들여야겠다.

 

🚨CODE

import java.util.*;
import java.io.*;

public class Solution {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int testCase = Integer.parseInt(br.readLine());
		
		for(int tc = 1; tc<=testCase; tc++) {
			int n = Integer.parseInt(br.readLine());
			int[] arr = new int[n];
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int i = 0; i<n; i++) {
				int num = Integer.parseInt(st.nextToken());
				arr[i] = num;
			}
			
			int max = arr[n-1];
			long sum = 0;
			
			for(int i = n-2; i >= 0; i--) {
				if(arr[i] < max) {
					sum += max - arr[i];
				}else {
					max = arr[i];
				}
			}
			
			bw.write(String.format("#%d %d\n", tc, sum));
		}// end tc
		
		bw.flush();
	}
}