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

0. 문제 링크

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

SW Expert Academy

 

1. 문제 설명

1) 예측된 매매가를 가지고 최대 수익을 내도록 판매하기

 

2. 입출력

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

// output
#1 0
#2 10
#3 5

 

3. 코드

import java.util.*;

public class swea1859 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt(); // 테스트 케이스의 개수
		
		for(int t = 1; t <= T; t++) {
			int N = sc.nextInt(); // 매매가의 개수
			int[] arr = new int[N]; // 매매가
			for(int n = 0; n < N; n++) {
				arr[n] = sc.nextInt();
			}
			
			long ans = 0L; // 수익
			long max = arr[N-1]; // 최대값
			
			for(int n = N-2; n >= 0; n--) {
				if(max > arr[n]) { // max가 현재 값보다 크면
					ans += max-arr[n]; // 매도
				} else { // max가 현재 값보다 작으면
					max = arr[n]; 
				}
			}
			
			StringBuilder sb = new StringBuilder();
			sb.append("#" + t + " " + ans + "\n");
			System.out.print(sb.toString());
		}
	}
}

 

 실행 결과

 

4. 회고

1) 런타임 에러가 났었는데 N의 범위(2 <= N <= 1,000,000)와 매매가(10,000)로 인해 백억 이상의 수가 예측되는데, 수익을 내는 ans가 값을 감당하지 못하기 때문에 long 타입으로 선언했다

2) 보통 배열 문제는 for 문으로 0번째 인덱스부터 하나씩 보는데, 이 문제의 경우에는 이미 매매가를 예측할 수 있기 때문에 마지막 인덱스부터 하나씩 보면서 정답을 찾을 수 있었다

 

5. Github

https://github.com/iihye/Algorithm/blob/main/SWEA/swea1859.java