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

백만 장자 프로젝트

시간이 너무 많이 걸려버린 문제..
결국 풀이를 봤다.

처음엔 최대값을 구해서 정렬하고..어쩌구 하는 방법을 생각했는데 그러면 당연히 시간도 많이 걸리고 풀이도 복잡함..

!!!!!!!!!!!!!! 정답코드아님 아까워서 올리는 코드
            //1. 정렬
            for (int i = 0; i < maxArr.length - 1; i++) {
                int max = i;
                for (int j = i; j < maxArr.length; j++) {
                    if (maxArr[j] > maxArr[max]) {
                        max = j;
                    }
                }
                swap(maxArr, i, max);
                swap(maxArrIndex, i, max);
            }

            int cnt = 0; // 산 갯수
            int result = 0; //이득
            int maxDay = maxArrIndex[0]; //시세가 제일 높은 날
            int maxDayArr = 0; //지금 몇번 째로 시세가 높은 날인지.

            // 시세가 가장 높은 날이 첫 날이 아니면 시작.
            // i = 오늘
            for (int i = 0; i < maxArr.length; i++) {
                //시세가 높은 날이 지났다면.. 다음 시세가 높은 날을 찾아보자.
                if (maxDay < i) {
                    //  maxArrIndex[maxDayArr + j]가 오늘(i)보다 큰 지 확인 해보자
                    // maxArrIndex의 길이 만큼 비교할 것이다..
                    for (int j = maxDayArr+1; j < maxArrIndex.length; j++) {
                        // 오늘보다 큰 day 중에 시세가 높은 날이 있더라 하면
                        if (maxArrIndex[j] >= i) {
                                maxDay = maxArrIndex[j];
                                maxDayArr = j;
                                break;
                        }
                        if (maxArrIndex[j] == maxArrIndex.length - 1) { // 배열의 끝이면
                            maxDay = -1; // 더이상 최대값이 없음을 명확하게 처리
                        }
                    }
                }

                if (maxDay != -1) {
                    // 오늘이 시세가 제일 높은 날이 아니면
                    if (i != maxDay) {
                        cnt++;
                        result -= arr[i];
                    } else { //오늘이 제일 시세가 높은 날이면
                        result += cnt * arr[i];
                        cnt = 0;
                    }
                }
            }

그래서 풀이 영상을 본 풀이

1. 첫날부터 시작해서 최댓값인 날을 구한다.
2. 최댓값인 날까지 (최댓값 - 그 날짜 가격) 을 더하기
3. 이제 그 다음 날부터 또 다른 최댓값인 날을 구하기
4. 반복

package SWEA.SelfStudyBook3.swStudy.basic1;

import java.io.*;
import java.util.Arrays;

public class problem_1859_solved_1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long T = Long.parseLong(br.readLine());

        for (int t = 1; t <= T; t++) {
            long N = Integer.parseInt(br.readLine());
            long[] arr = Arrays.stream((br.readLine()).split(" ")).mapToLong(Long::parseLong).toArray();

            long ans = 0;
            int s = 0;
            while(s<N){
                int i_max =s;
               for(int i =s+1; i<N; i++){
                   if(arr[i_max]<arr[i]){
                       i_max = i;
                   }
               }
               for(int i=s;i<i_max;i++){
                   ans += (arr[i_max] - arr[i]);
               }
               s=i_max+1;
            }
            bw.write("#"+t+" " +ans+"\n");
        }
        bw.flush();
        bw.close();
    }
}

이 코드의 문제점: int 배열 값이 1000000일 때는 작동이 안된다. (시간초과)
최악의 경우 시간 복잡도 O(n^2)

그래서
풀이2. 뒤에서 부터 한번만 순회
시간 복잡도 O(n)으로 만든다.

import java.io.*;
import java.util.Arrays;
import java.util.List;


public class problem_1859_solved_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long T = Long.parseLong(br.readLine());

        for (int t = 1; t <= T; t++) {
            int N = Integer.parseInt(br.readLine());
            long[] arr = Arrays.stream((br.readLine()).split(" ")).mapToLong(Long::parseLong).toArray();
            long ans = 0;
            long max =0;

            for(int i=N-1; i>=0; i--){
                if(max < arr[i]){
                    max =arr[i];
                }else{
                    ans +=(max - arr[i]);
                }
            }

            bw.write("#"+t+" " +ans+"\n");
        }
        bw.flush();
        bw.close();
    }
}