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

전체 코드

package algorithm;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class SWEA_백반장자프로젝트 {

	static int T, N, arr[], idx;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		Queue<Integer> q;
		
		for (int test = 1; test <= T; test++) {
			q = new LinkedList<Integer>();
			N = sc.nextInt();
			arr = new int[N];

			for (int i = 0; i < N; i++)
				arr[i] = sc.nextInt();

			idx = 0;
			int MAX_idx, tmp;
			long result = 0;
			while (idx < N-1) { // 인덱스가 N-1로 갈때까지 진행
				MAX_idx = getMaxIdx(); // 현재 인덱스부터 배열의 끝까지 중 최대값의 인덱스를
				if (MAX_idx == 0)
					break;
				
				for (; idx < MAX_idx; idx++) { // 현재부터 최대값전까지 q에 삽입
					q.add(arr[idx]);
				}
				
				while(!q.isEmpty()) {
					tmp = q.poll();
					result += arr[idx] - tmp; // 여기서 idx는 최대값의 idx이며 최대값에서 q에삽입된 값들을 빼며 누적시킨다.
				}
				idx++;
			}

			System.out.println("#" + test + " " + result);

		}
	}
	
	private static int getMaxIdx() {
		int MAX = -1;
		int MAX_idx = 0;
		for (int i = idx; i < N; i++) { // 현재 인덱스부터 끝까지 중 최대값의 인덱스를 추출
			if (MAX < arr[i]) {
				MAX = arr[i];
				MAX_idx = i;
			}
		}
		return MAX_idx;
	}

}

 

문제 핵심 코드

idx = 0;
int MAX_idx, tmp;
long result = 0;
while (idx < N-1) { // 인덱스가 N-1로 갈때까지 진행
	MAX_idx = getMaxIdx(); // 현재 인덱스부터 배열의 끝까지 중 최대값의 인덱스를
	if (MAX_idx == 0)
		break;
	
	for (; idx < MAX_idx; idx++) { // 현재부터 최대값전까지 q에 삽입
		q.add(arr[idx]);
	}
	
	while(!q.isEmpty()) {
		tmp = q.poll();
		result += arr[idx] - tmp; // 여기서 idx는 최대값의 idx이며 최대값에서 q에삽입된 값들을 빼며 누적시킨다.
	}
	idx++;
}

 

최대값의 인덱스를 구하고 그 전까지 queue에 삽입 후 최대값에서 뺀 값들을 누적시키는 방식을 계속해서 진행했다.

풀이를 하며 스택으로 풀면 더 좋을 것 같다고 생각했다.