[백준] 11501 주식 - Greedy / Java

• 문제 링크

11501번: 주식

 

• 풀이 과정

각 날짜를 기준으로 현재 주가보다 추후에 주가가 더 상승하는 날이 존재하는 지 확인한다.

이를 위해 반복문을 역으로 돌려 마지막 날부터 확인한다.

 

현재 주가가 최고 주가를 저장할 max 보다 크다면 해당 날짜의 주가로 max 를 갱신하고,

현재 주가가 max 보다 작다면 해당 날짜를 기준으로 이후에 주가가 더 오르는 날이 존재하게 된다.

따라서 이 때 주식을 하나 구매하고 마지막 날부터 확인하여 구해진 max 일 때 판매하면 최대 수익을 볼 수 있으므로

max - 현재 주가(stock[i]) 를 전체 수익 earn 에 더한다.

 

위와 같은 과정을 거쳐 각 테스트 케이스의 전체 수익을 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

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

        int t = Integer.parseInt(br.readLine());

        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int[] stock = new int[n];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++)
                stock[i] = Integer.parseInt(st.nextToken());

            int max = 0;
            long earn = 0;
            for (int i = n - 1; i >= 0; i--) {
                if (stock[i] > max)
                    max = stock[i];
                else
                    earn += max - stock[i];
            }

            bw.write(earn + "\n");
        }

        bw.flush();
    }

}