[백준] 11501. 주식

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

11501번: 주식

처음에는 입력 값을 배열에 넣은 뒤 배열의 앞에서부터 순차적으로 순회하니 조금 복잡해졌다. 그런데 배열의 뒤에서부터 순회하면 훨씬 깔끔하다.

• 배열의 뒤에서부터 순회해서 max와 arr[j]를 비교한다.
  • max < arr[j]인 경우, max 값을 arr[j]로 갱신한다.
  • max >= arr[j]인 경우, answer에 max-arr[j] 값을 더해준다. (arr[j]를 max 값에 팔아 수익을 내는 것이다.)
• 뒤에서부터 배열을 한 번 순회하기 때문에 O(N)의 시간 복잡도가 발생한다.
• 주의할 점은 answer에 값이 더해지면서 int 범위를 넘을 수 있으므로 long 형으로 선언해야 한다.

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

import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 시간복잡도: O(N) = 1,000,000
public class Main {

    static int t;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            // 입력 및 배열 초기화
            n = Integer.parseInt(br.readLine());
            int[] arr = new int[n + 1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
            }

            // 주요 로직
            long answer = 0;
            int maxPrice = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (maxPrice < arr[j]) {
                    maxPrice = arr[j];
                } else {
                    answer += maxPrice - arr[j];
                }
            }

            System.out.println(answer);
        }
    }
}

 반복문을 배열의 뒤에서부터 도는 것도 방법이다..! 유연하게 생각하자..