11501 - 주식[S2]

 

문제

https://www.acmicpc.net/problem/11501

 

홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다.

1. 주식 하나를 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안한다.

홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다.

예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이 된다.

풀이

 

전열 순회 사용

초기에는 다음과 같은 '전열 순회' 규칙을 생각했었다.

1. 첫 인덱스(0) 부터 조회하여 '고점' 의 인덱스(h)를 찾는다.

2. [0, h - 1]사의의 값과 고점의 가격 차가 곧 수익이다.

3. h + 1인덱스부터 조회하여 다시 '고점'을 찾는다 (1~2 반복)

 

하지만 이 경우, N, N-1, N-2 ... 0의 하향식 상황에서 최악의 시간복잡도를 가지게 된다. (N^2)

이는 최대 100만의 경우에서 시간 초과로 이루어진다.

 

후열 순회 사용

이를 해결하기 위해 다음과 같은 공식을 사용하였다.

 

 

1. 뒤에서부터 순회 시작: 마지막 날의 주가를 초기 고점(maxPrice)으로 설정한다.

2. 매일 주가를 보며 현재 주가가 maxPrice보다 작다면, 그 차이만큼 이익을 계산해 더해준다. 그렇지 않다면 maxPrice를 갱신하여, 현재 주가를 새로운 고점으로 설정한다.

3. 위 과정을 반복하면서 얻은 총 이익이 최대 이익이 된다.

 

 

이렇게 한다면 단 한번의 O(N) 순회로 문제를 해결할 수 있다.

코드

 

import java.io.*;
import java.util.*;
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());

            int[] input = new int[n];
            for (int i = 0; i < n; i++) {
                input[i] = Integer.parseInt(st.nextToken());
            }
            solve(n, input);
        }
    }

    //후열 순회
    static void solve(int n, int[] input) {
        long earn = 0;

        int lastPrice = input[n - 1];
        for (int i = n - 1; i >= 0; i--) {
            int nowPrice = input[i];
            if(nowPrice < lastPrice) earn += (lastPrice - nowPrice);
            else if(nowPrice > lastPrice) lastPrice = nowPrice;
        }
        System.out.println(earn);
    }

}