[Java] SW Expert. 백만 장자 프로젝트

✖️ 처음 생각했던 풀이
1. 매매가 List 내에서 최댓값을 찾는다.
2. 최댓값보다 index가 앞쪽일 경우 수익+=(최댓값-매매가)
3. 최댓값보다 index가 뒤쪽일 경우 새로운 최댓값을 찾아서 2번과 같이 계산한다.

📌 페어분이 알려주신 풀이
1. 매매가 List 끝의 값을 최대값으로 설정한다.
2. 앞쪽으로 탐색하면서 매매가<최대값일 경우 수익+=(최댓값-매매가),
3. 매매가>최대값일 경우 새로운 최대값으로 설정

 

문제 설명

1. 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
2. 하루에 최대 1만큼 구입할 수 있다.
3. 판매는 얼마든지 할 수 있다.

제한 사항

시간: 10개 TestCase를 합쳐서 30초 이내

메모리: 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스 별로 첫 줄에는 자연수 N(2≤ N ≤ 1,000,000)이 주어지고,

둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.

각 날의 매매가는 10,000 이하이다.

출력

각 테스트 케이스마다 ‘#X’(X는 테스트 케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.

예제 입력

3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

예제 출력

#1 0
#2 10
#3 5

풀이(Fail; 시간 초과)

30,006ms, 62,464KB

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
import java.io.FileInputStream;

class Solution
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        ArrayList<Integer> cost = new ArrayList<>();
 
        int T = Integer.parseInt(br.readLine());
 
        for(int i=0; i<T; i++) {
            long result = 0;
            int day = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            while(st.hasMoreTokens()) {
                cost.add(Integer.parseInt(st.nextToken()));
            }
            int max = Collections.max(cost);
            for(int j=0; j<day-1; j++) {
                if(j<cost.indexOf(max))
                    result += max-cost.get(j);
                else {
                    for(int k=day-1; k>j; k--) {
                        if(cost.get(k)-cost.get(j)>0) result+=cost.get(k)-cost.get(j);
                    }
                }
                System.out.println(result);
            }
            sb.append("#").append(i+1).append(" ").append(result).append("\\n");
            cost.clear();
        }
 
        System.out.println(sb.toString());
    }
}

풀이(Pass; 역순으로 탐색)

741ms, 139,140kB

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
import java.io.FileInputStream;

class Solution
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        ArrayList<Integer> cost = new ArrayList<>();
 
        int T = Integer.parseInt(br.readLine());
 
        for(int i=0; i<T; i++) {
            long result = 0;
            int day = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            while(st.hasMoreTokens()) {
                cost.add(Integer.parseInt(st.nextToken()));
            }
 
            int max = cost.get(cost.size()-1);
            for(int j=day-2; j>=0; j--) {
                if(cost.get(j)<max) result += max-cost.get(j);
                else max = cost.get(j);
            }
            sb.append("#").append(i+1).append(" ").append(result).append("\\n");
            cost.clear();
        }
 
        System.out.println(sb.toString());
    }
}