[Baekjoon 11501] 주식 문제풀이 - JAVA

[Silver II] 주식 - 11501

문제 링크

성능 요약

메모리: 313940 KB, 시간: 1104 ms

분류

그리디 알고리즘(greedy)

문제 설명

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

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

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

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

입력

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

출력

각 테스트케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다. 답은 부호있는 64bit 정수형으로 표현 가능하다.

문제 풀이

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

import java.util.StringTokenizer;

public class Main {

    static StringBuilder sb = new StringBuilder();

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

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

        while(T -- > 0) {
            int N = Integer.parseInt(br.readLine());
            int stocks[] = new int[N];
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < N; i ++) {
                stocks[i] = Integer.parseInt(st.nextToken());
            }

            long max = 0;
            long answer = 0;
            for(int i = N - 1; i >= 0; i --) {
                if(stocks[i] > max) {
                    max = stocks[i];
                } else {
                    answer += max - stocks[i];
                }
            }

            sb.append(answer + "\n");
        }

        System.out.println(sb);
    }
}

코드 풀이

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

        while(T -- > 0) {
            int N = Integer.parseInt(br.readLine());
            int stocks[] = new int[N];
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < N; i ++ ) {
                stocks[i] = Integer.parseInt(st.nextToken());
            }

T에 테스트 케이스가 들어가고 while을 통해 테스트 케이스가 0이 될때까지 돌려준다.

각 테스트 케이스에는 날의 수를 나타내는 N이 들어오면 날자에 맞는 주식의 가격을 저장할 stocks배열을 선언하였다.

이후 for문을 이용해서 stocks 배열에 주식의 값을 넣어주었다.

            long max = 0;
            long answer = 0;
            for(int i = N - 1; i >= 0; i -- ) {
                if(stocks[i] > max) {
                    max = stocks[i];
                } else {
                    answer += max - stocks[i];
                }
            }

            sb.append(answer + "\n");

max는 가장 큰 가격을 저장할 변수로 선언했고, asnwer은 StringBuilder에 넣어줄 테스트 케이스별 정답을 저장할 변수로 선언했다.

주식의 가장 마지막날부터 첫날까지 역순으로 for문이 돌도록 하고 만약 해당 날짜에 주식이 최대값보다 크다면 최대값을 바꿔주고, 최대값이 크다면 정답에 최대값에서 현재 날짜의 주식값을 뺀 값을 answer에 넣었다.

이후 sb.append를 사용해 StringBuilder에 answer을 넣어주면 한개의 테스트 케이스가 끝난다.