[SWEA] D2 - 1859번 | 백만 장자 프로젝트

🔍 문제 보러 가기

원재는 미래를 보는 능력을 통해 매매가를 미리 알고 있어, N일 동안 최대 이익을 낼 수 있는 방법을 찾고자 한다. 다만 하루에 최대 1만큼만 물건을 구입할 수 있고, 판매는 제한 없이 가능하다. 최대 이익을 구하는 문제

문제 상세 설명

내 코드

package D2;

//SWEA D2 1859번 "백만 장자 프로젝트" 문제 풀이 

import java.util.*;

public class N1859 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int T = scan.nextInt();
		
		Sol2 sol = new Sol2();
		
		for(int i = 1; i <= T; i++) {
			int N = scan.nextInt();
						
			List<Integer> list = new ArrayList<>();
			for(int j = 0; j < N; j++) {
				list.add(scan.nextInt());
			}
			
			System.out.printf("#%d %d\n", i, sol.solution(list));
			
		}
	}
}

class Sol2 {
	

	public long solution(List<Integer> list) {
		
		int start_idx = 0; 
		int end_idx = maxOfList(start_idx, list);
		
		long profit = 0;
		
		while(true) {
			profit += calculation(start_idx, end_idx, list);
			
			if (end_idx == list.size() - 1) break;
			
			start_idx = end_idx + 1;
			end_idx = maxOfList(start_idx, list);
						
		}
		
		return profit;
	}
	
	public long calculation(int start_idx, int end_idx, List<Integer> list) {
		
		long profit = 0;
		int cnt = 0;
		
		for(int i = start_idx; i < end_idx; i++) {
			profit -= list.get(i);
			cnt++;
		}
		
		profit += cnt * list.get(end_idx);

		
		return profit;
	}
	
	// 리스트에서 최대 값의 index를 구함 
	public int maxOfList(int sidx, List<Integer> list) {
		
		int max = 0;
		int idx = -1;
		for (int i = sidx; i < list.size(); i++) {
			if (list.get(i) > max) {
				max = list.get(i);
				idx = i;
			}
		}
		return idx;
	}
	
}

접근 방법

최대 이익을 얻기 위해, 매매가 리스트에서 현재 시점의 최대값을 기준으로 물건을 구매하고 판매하는 방식으로 접근한다.

1. 최대값 인덱스 찾기

   주어진 매매가 리스트에서 현재 구간의 최대값 인덱스를 찾는다.

2. 이익 계산

   profit 변수에 이익을 저장한다.

   최대값이 나오는 인덱스 전까지 물건을 하루에 하나씩 구매한다.

   구매한 날들의 매매가를 profit에서 차감해 profit -= 구매가로 기록한다.

   구매한 물건의 개수를 기록해둔다.

3. 최대값 인덱스 날에 모두 판매

   최대값인 날에는 지금까지 구매한 모든 물건을 판매한다.

   판매 이익은 구매한 횟수 X 최대 가격 으로 계산해 profit 에 더한다.

4. 반복

   다음 시작 인덱스를 현재 최대값 인덱스 + 1 로 저장한다.

   이 새로운 구간에서 최대값을 다시 찾고, 위의 과정을 반복해 전체 리스트를 처리한다.

point

profit 변수의 타입을 int로 설정하고 코드를 실행했지만, 테스트 케이스를 통과하지 못했다. 값이 초과될 수 있다는 점을 놓쳤던 것이다. int를 long으로 변경하니 통과할 수 있었다. 타입 체크를 꼭 신경 써야겠다.

개선 코드

package D2;

//SWEA D2 1859번 "백만 장자 프로젝트" 문제 풀이 개

import java.util.*;

public class N1859_b {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int T = scan.nextInt();
		
		StringBuilder result = new StringBuilder();
		
		for(int i = 1; i <= T; i++) {
			int N = scan.nextInt();
			
			int[] prices = new int[N];
			for(int j = 0; j < N; j++) {
				prices[j] = scan.nextInt();
			}
			result.append(String.format("#%d %d\n", i, solution(prices)));
		}
		
		
		System.out.print(result);
		scan.close();
	}
	
	public static long solution(int[] prices) {
		long profit = 0;
		int maxPrice = 0;
		
		// 역순으로 탐색하면서 최대 가격을 유지 
		for(int i = prices.length - 1; i >= 0; i--) {
			if (prices[i] > maxPrice) {
				maxPrice = prices[i];
			} else {
				profit += maxPrice - prices[i];
			}
		}
		return profit;
	}
}

Point

1. 역순 탐색

   이전 코드에서 maxOfList는 매번 최대값을 찾기 위해 리스트의 나머지 요소를 모두 탐색한다. 이 방식은 최악의 경우 O(N^2)의 시간 복잡도를 유발할 수 있다.

   매매가 리스트의 끝날부터 시작해 첫날까지 거꾸로 탐색한다.

   현재 시점에서 미래의 가격을 모두 알고 있는 상황을 가정할 수 있기 때문에 가능한 접근 방식이다.

   역순으로 탐색할 경우, 현재 위치 이후의 최대값을 항상 알고 있는 상태로 계산할 수 있어, 별도의 중첩 루프 없이 최적의 이익을 얻을 수 있다.

2. 최대값 갱신 및 이익 누적

   현재까지 탐색한 구간의 최대 매매가를 maxPrice 변수에 저장해 두고, 다음날로 넘어가기 전에 가격을 비교해 이익을 계산한다.

   현재 탐색 중인 매매가가 maxPrice보다 낮다면, 해당 날에 매수하여 maxPrice에 판매했을 때 얻는 이익(maxPrice - prices[i])를 profit에 누적한다.

   만약 현재 매매가가 maxPrice보다 높다면, 새로운 maxPrice로 설정하고, 이후의 날들에 대해 이 가격을 기준으로 다시 이익을 계산한다.

3. 누적 이익 계산

   최대값보다 낮은 가격에서 매수했을 때 이익을 누적하는 방식으로, 한 번의 루프로 모든 날을 처리해 최종 이익을 계산한다.

   이 과정은 역순으로 단일 루프에서 이루어지므로 시간복잡도는 O(N)이다.

매매가가 [1, 1, 3, 1, 2] 인 경우
뒤에서부터 역순으로 진행

1	1	3	1	2
maxPrice = 3	maxPrice = 3	maxPrice = 3	maxPrice = 2	maxPrice = 2
profit = 3 + 3 - 1	profit = 1 + 3 - 1	profit = 1	profit = 2-1	profit = 0

따라서, profit = 5