Q 1859. 백만 장자 프로젝트(D2)

Q 1859. 백만 장자 프로젝트(D2)

 

0. 문제

 

D2 난이도의 문제이고, 단순한 배열 순회 문제라고 생각된다.

매일 매일 물건의 가격이 주어진다. 하루에 물건은 하나만 살 수 있고, 파는 수량은 제한이 없다.이 때 최대 이익을 출력하는 문제이다.

---

1. 풀이

 

처음에 투 포인터나 정렬을 이용한 문제인가? 라는 생각을 했었는데,

단순하게 생각을 뒤집어서 맨 뒤에서 앞으로 배열을 조회하면 해결할 수 있었다.

1) 배열의 맨 뒤에서 앞으로 순회한다.

1-1) 이 때 만약 기존 최대 가격보다 큰 가격을 만날 경우 그 값을 저장한다.

1-2) 그렇지 않은 경우 기존 최대 가격 - 현재 가격을 결과값에 저장한다.

 

import java.util.Scanner;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

class Solution
{

	static Scanner scanner;
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuffer sb = new StringBuffer();
	static int[] arrN;
	static int N;
	
	static void input() throws IOException
	{
		N = Integer.parseInt(br.readLine()); 
		arrN = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arrN[i] = Integer.parseInt(st.nextToken());  
		}
	}
	
	static void pro(int tc) {

		int prevMax = arrN[N-1];
		long res = 0;
		for (int i = N-2; i >= 0; i--) {
			if (prevMax > arrN[i]) {
				res += prevMax - arrN[i];
			} else {
				prevMax = arrN[i];
			}
		}
		
		sb.append('#').append(tc).append(' ').append(res).append('\n');
	}
	
	
	
	public static void main(String args[]) throws Exception
	{
		
//		System.setIn(new FileInputStream("res/input.txt"));
//		scanner = new Scanner(System.in);
//		int T = scanner.nextInt();
		int T = Integer.parseInt(br.readLine());
		for(int test_case = 1; test_case <= T; test_case++)
		{
			input();
			pro(test_case);
		}
		System.out.println(sb);

	}
}

---

2. 시간복잡도 계산

 

0) N의 최대값은 1,000,000이다.

1) 처음 입력값(가격) 저장 - O(N)

2) 풀이 1번 - O(N)

따라서 시간복잡도는 O(2N)이고, 시간제한은 20초이므로

1초에 약 1억번 연산을 한다고 가정하면, 1초 이내에 풀 수 있다.

---