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

< 문제 >

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

SW Expert Academy

< 처음 풀이 >

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

class Solution {
	// 백만장자 프로젝트 
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int test_case=Integer.parseInt(br.readLine());
		
		for(int t=1;t<=test_case;t++) {
			int n=Integer.parseInt(br.readLine()); //n일 동안
			int arr[]=new int[n];
			
			StringTokenizer st=new StringTokenizer(br.readLine());
			for(int i=0;i<n;i++) {
				arr[i]=Integer.parseInt(st.nextToken()); //배열에 값을 입력받음
			}
			
			int profit=0;
			for(int i=0;i<n;i++) {
				int max=arr[i]; //지금 현재 값을 최대로 설정
				for(int j=i+1;j<n;j++) {
					max=Math.max(max, arr[j]); //현재 값보다 뒤에 있는 값 중에 가장 큰 값 찾기 
				}
				profit+=(max-arr[i]);
			}
			System.out.println("#"+t+" "+profit);
		}
	}

}

 

➡️ 처음에는 현재 값을 중심으로, 현재 값보다 뒤에 있는 값들 중에 가장 큰 값을 찾고, 그 가장 큰 값에서 현재 배열의 값을 빼서 저장하는 방식으로 정답을 구하려고 했다. 하지만 배열의 최대 크기가 1,000,000 인데 매 반복마다 2중 반복문을 돌다보니 제한시간 초과로 통과하지 못했다. 

< 올바른 풀이 >

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

public class Solution {
	// 백만장자 프로젝트 
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int test_case=Integer.parseInt(br.readLine());
		
		for(int t=1;t<=test_case;t++) {
			int n=Integer.parseInt(br.readLine()); //n일 동안
			int arr[]=new int[n];
			int max_arr[]=new int[n];
			
			StringTokenizer st=new StringTokenizer(br.readLine());
			for(int i=0;i<n;i++) {
				arr[i]=Integer.parseInt(st.nextToken()); //배열에 값을 입력받음
			}
			
			int max=0;
			for(int i=n-1;i>=0;i--) {
				max=Math.max(max,arr[i]);
				max_arr[i]=max;
			}
			
			long profit=0;
			for(int i=0;i<n;i++) {
				if(arr[i]<max_arr[i])
					profit+=(max_arr[i]-arr[i]);
			}
			System.out.println("#"+t+" "+profit);
		}
	}

}

 

✏️ 풀이 방법

 

1. 값을 저장하는 배열 arr 과 현재 배열 인덱스에서의 최댓값을 저장하기 위한 배열 max_arr 을 생성한다.

2. 배열을 뒤에서부터 돌며 최댓값을 찾아 max_arr 에 저장한다. 

=> 예를 들어, 1 1 3 1 2 의 경우 앞에서부터 최댓값을 구하면, max 의 값은 이전 max의 값에 영향을 받기 때문에, max_arr[0] =3, [1]=3, [2]=3, [3]=3, [4] =3 으로 우리가 원하는 값이 저장되지 않는다. 즉, 앞에서부터 반복문을 돌면 앞에 가장 큰 수가 나왔을 때 뒤의 값들의 최댓값은 변하지 않으므로, 뒤에서부터 반복문을 돌아 최댓값이 적절하게 바뀔 수 있도록 코드를 구성해야한다. 

3. 배열의 반복문을 돌며, 현재 값(arr[i])이 현재 값에서의 최댓값보다 작다면, 그 둘의 차를 profit 변수에 저장한다.

4. profit 변수 출력

 ⚠️ 주의할 점

 N의 최댓값은 1,000,000 이고, 매매가의 최댓값은 10,000 이다. 그러면 최대 1000000 * 10000 이 되므로 int의 범위를 초과하게 되어 long 으로 선언해 주어야 한다! 

 

✍🏻 느낀점

 

옛날에 풀어봤던 문제였는데, 그 때 다른 사람의 풀이를 보고 풀었던 것 같아서 내 힘으로 풀려고 노력했다. 근데 시간초과가 나서ㅎㅎ,,  또 참고를 해서 풀었지만 저번에는 왜? 에 집중을 하지 않았는데 이번에는 왜 뒤에서부터 반복문을 돌아야하는지, 왜 시간초과가 났는지, 왜 long형으로 선언을 해야하는지 혼자 생각을 해봤더니 저번보다 이해를 깊게 한 것 같다. 답만 얻는 것이 중요한 게 아니라 효율적으로 푸는 것도 중요하다는 걸 또 깨닫게 해준 문제였다.