[SWEA] 백만 장자 프로젝트 (+오답)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1

 

(오답)

		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();


		for(int test_case = 1; test_case <= T; test_case++)
		{
			int N = sc.nextInt();
            int[] array = new int[N];
            int diff1;
            int diff2;
            int sum =0 ;
            
            for(int i=0; i<N; i++){
                array[i] = sc.nextInt();
            }
            
            for(int j=0; j<N; j++){
                diff1=0;
                diff2=0;
                for(int k=j+1; k<N; k++){
                    if(array[j]<array[k])
                        diff1 = array[k] - array[j];
                    if(diff1>diff2)
                        diff2 = diff1;
                }
                sum+=diff2;
            }
            System.out.println("#" + test_case + " " + sum);
		}
	}
}

 

정답률이 D2인데 33%에 육박하는 문제.. 이유가 뭘까?

 

힌트) input값이 매우 많아서 SWEA에서 제출 전에 Run을 눌러볼 수도 없다

1. 총 이득이 2147483647원을 넘기 때문에 int를 사용하면 안된다

 > long 사용하면 됨(sum)

 

2. D1~D2 정도의 문제에서는 고려할 필요 없었지만, 2번 반복하면서 돈 차이를 비교하고 다음으로 넘어가고 그게 최댓값인지 확인하고~를 반복하면 너무 많이 반복해야하는 상황이 나오기 때문에 제한시간에 걸리게 된다

 >  앞에서부터 반복할 시 금액이 올랐다가 내려가는 상황을 체크해야 되서 2번인건데, 뒤에서부터 확인하면 반복문 1번으로 max - 현재값 확인, 갱신으로 풀 수 있다.

 

(정답)

import java.util.Scanner;
import java.io.FileInputStream;


class Solution
{
	public static void main(String args[]) throws Exception
	{
	
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();


		for(int test_case = 1; test_case <= T; test_case++)
		{
			int N = sc.nextInt();
            int[] array = new int[N];
            long sum=0;
            int max =0 ;
            
            for(int i=0; i<N; i++){
                array[i] = sc.nextInt();
            }
            for(int j=N-1; j>=0; j--){
                if(max<array[j])
                    max = array[j];
                else if(max>array[j])
                    sum+=max-array[j];
            }
	
            System.out.println("#" + test_case + " " + sum);
		}
	}
}

 

나도 낮은 정답률에 기여한 문제였다.