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

링크

SWEA[1859]

문제설명

• {문제설명}

문제풀이

• O(N^2)->O(N)

문제코드

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

public class Solution {
    public static void main(String[] args) throws FileNotFoundException {
        //System.setIn(new FileInputStream("res/swea/1859.txt"));
        Scanner sc = new Scanner(System.in);

        int T=sc.nextInt();
        for (int test_case = 1; test_case <= T; test_case++) {
            long ans=0;
            int N = sc.nextInt();
            int[] price = new int[N];
            for (int i = 0; i < N; i++) {
                price[i]=sc.nextInt();
            }

            int max=price[0];
            int start=0;
            int max_idx=0;
            while(true) {
                for (int i = start; i < N; i++) {
                    if(max<=price[i]) {    //동일한 max 중에서도 가장 오른쪽 max를 고려
                        max=price[i];
                        max_idx=i;
                    }
                }
                for (int i = start; i < max_idx; i++) {
                    ans+=max-price[i];
                }
                if(max_idx == N-1)break;
                start=max_idx+1;
                max=price[start];
            }

            System.out.println("#"+test_case+" "+ans);
            /*
             * 초기화
             */
        }//end test_case
    }//end main
}//end class

아쉬운점

• O(n)고려 안했음, 컴퓨터를 너무 믿은 죄
  • 무식하게 N^2 할 경우 10^12가 나와서 시간초과 뜸
  • 10^9 = 1
• 1 이 999,999 개 나오고 맨 마지막에 10000이 나온다면, 최종 결과는 9999 * 999,999 = 9,998,990,001이 되므로 int범위를 넘어가서 long 타입 사용.

잘한점

• O(N^2)->O(N)으로 바꿈
  • max 기준으로 나눠서 다시 구함