백준 11501 - 주식 (자바 - 그리디)

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

11501번: 주식

 

* 문제 요약

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

매일 그는 아래 세 가지 중 한 행동을 한다.

1. 주식 하나를 산다.

2. 원하는 만큼 가지고 있는 주식을 판다.

3. 아무것도 안 한다.

 

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

예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6 일 때, 주가가 계속 감소하므로 최대 이익은 0 이 된다.

그러나 만약 날 별로 주가가 3, 5, 9 일 때는 처음 두 날에 주식을 하나씩 사고 마지막 날 다 팔아버리면 이익이 10이 된다.

 

* 입력

입력의 첫 줄에는 테스트 케이스 수를 나타내는 자연수 T 가 주어진다.

각 테스트 케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N (2 <= N <= 1,000,000) 이 주어지고, 둘째 줄에는 날 별 주가를 나타내는 N 개의 자연수들이 공백으로 구분되어 순서대로 주어진다.

날 별 주가는 10,000 이하다.

 

* 출력

각 테스트 케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다.

답은 부호있는 64bit 정수형으로 표현 가능하다.

 

* 예시

 

* 해결 과정

앞전에 비슷한 문제를 풀어본 경험이 있어 생각보다 쉽게 풀어낸 문제이다.

테스트 케이스 별로 각 날짜벼 주식값이 들어오면 해당 값들을 배열에 저장한 다음 아래와 같은 로직을 수행한다.

 

1. 배열의 가장 뒤에서부터 탐색을 시작하며, 현재까지 탐색한 주식의 최고값은 max 변수에 저장해둔다.

초기에 max 에는 int 자료형의 최소값이 저장되어 있다.

2. 만약 현재 탐색중인 값이 max 에 저장된 값 보다 크다면 max 변수 값을 현재 탐색중인 값으로 저장된다.

3. 만약 현재 탐색중인 값이 max 보다 작거나 같다면 앞전에 미리 찾아낸 max 변수 값만큼 주식이 올랐을 때 팔면 이익을 볼 수 있다는 뜻이므로 max - 현재 탐색중인 주식 가격 결과를 결과 변수 result 에 합산해준다.

4. 배열에 대한 탐색이 종료되고 나면 그때까지 합산된 result 값을 결과를 출력하기 위한 배열 resultArray 에 저장해준 후 다음 테스트 케이스로 넘어간다.

 

* 코드

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int tc = Integer.parseInt(br.readLine());
        long[] resultArray = new long[tc];
        for (int i = 0; i < tc; i++) {
            int size = Integer.parseInt(br.readLine());
            int[] stockArray = new int[size];

            String[] input = br.readLine().split(" ");
            for (int index = 0; index < input.length; index++) {
                stockArray[index] = Integer.parseInt(input[index]);
            }

            long result = 0;
            int max = Integer.MIN_VALUE;
            for (int index = stockArray.length - 1; index >= 0; index--) {
                if (stockArray[index] > max) {
                    max = stockArray[index];
                } else {
                    result += (max - stockArray[index]);
                }
            }

            resultArray[i] = result;
        }

        for (long number : resultArray) {
            bw.write(number + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 배열을 뒤에서부터 탐색하며 현재 탐색한 주식 값과 현재까지 탐색된 주식들 중 가장 비싼값과 비교하여 어느쪽이 크냐에 따라 적절한 로직을 수행해줬다.

선택된 해답이 조건을 만족하는지 검사한다. -> 배열을 모두 탐색하기 전엔 최대 이익에 가장 가까운 값을 얻을 수 없으므로 배열 끝까지 탐색을 진행하며 계속 로직을 수행한다.

 

위의 과정을 통해 문제를 해결하였으므로 그리디 알고리즘 문제에 해당된다.