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

문제 설명

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

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

SW Expert Academy

풀기 전 생각

• 배열에 값을 다 넣은 후 최댓값(max)과 그에 해당하는 인덱스(maxIndex) 찾기
• 그 사이 원소의 갯수는 cnt = maxIndex - start
• 시작점(start)부터 최대값-1까지 값들을 sum에서 빼주기
• 그 후 최댓값일 때 판매로 벌어들인 수익 더해주기 (sum += cnt * max)
• 그다음 최댓값을 찾는 시작점은 maxIndex + 1
• 최댓값은 다시 0으로 초기화

코드

import java.math.BigInteger;
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 day = sc.nextInt();
            int[] price = new int [day];
            for(int i = 0; i < day; i++){ // 배열에 넣기
                price[i] = sc.nextInt();
            }
            int max = 0;
            int maxIndex = 0;
            int sum = 0;
            int start = 0;
            int findMaxIndex = 0;
            while(true){

                if(findMaxIndex >= day){break;} // 배열을 넘어가면 종료

                for(; findMaxIndex < day; findMaxIndex++){  // 최대값 찾기 (maxIndex랑 max)
                    if(price[findMaxIndex] > max){ max = price[findMaxIndex]; maxIndex = findMaxIndex;}
                } 

                int cnt = maxIndex - start; // 구입한 물건 갯수 구하기

                for(;start < maxIndex; start++) { 
                      sum -= price[start]; // 시작점부터 max 전까지 구매 비용 빼기
                }
                
                sum += max * cnt; // 팔고 남은 수익값 더해줌
                
                start = maxIndex + 1; //start++; // 다음 시작값은 maxIndex + 1
                findMaxIndex = start; // 다음은 start부터 시작하여 max를 찾음 
                max = 0; // 그 다음 최대값을 찾기 위해 0으로 초기화
            }
            System.out.println("#" + test_case +" " +  sum);
        }
    }
}

오류 및 개선

• 10개중 7개만 통과
• 댓글을 보니 범위가 커 int 범위를 넘어가는 오류가 발생

최종 코드

import java.math.BigInteger;
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 day = sc.nextInt();
            int[] price = new int [day];
            for(int i = 0; i < day; i++){ // 배열에 넣기
                price[i] = sc.nextInt();
            }
            int max = 0;
            int maxIndex = 0;
            BigInteger sum = BigInteger.valueOf(0);
            int start = 0;
            int findMaxIndex = 0;
            while(true){

                if(findMaxIndex >= day){break;} // 배열을 넘어가면 종료

                for(; findMaxIndex < day; findMaxIndex++){ // 최대값 찾기 (maxIndex랑 max)
                    if(price[findMaxIndex] > max){ max = price[findMaxIndex]; maxIndex = findMaxIndex;}
                }  

                int cnt = maxIndex - start; // 구입한 물건 갯수 구하기

                for(;start < maxIndex; start++) { 
                    sum = sum.subtract(BigInteger.valueOf(price[start])); // 시작점부터 max 전까지 구매 비용 빼기
                }

                sum = sum.add(BigInteger.valueOf(max * cnt)); // 팔고 남은 수익값 더해줌

                start = maxIndex + 1; //start++; // 다음 시작값은 maxIndex + 1
                findMaxIndex = start; // 다음은 start부터 시작하여 max를 찾음
                max = 0; // 그 다음 최대값을 찾기 위해 0으로 초기화
            }
            System.out.println("#" + test_case +" " +  sum);
        }
    }
}

BigInteger도 공부해 두자!