[백준/JAVA] 11501번: 주식

📖 문제

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

 

 

 

💡  풀이 방식

• 그리디

1. 주식 시세 정보를 저장한다.

2. 주식 정보를 역방향으로 탐색하며 최대 이익 값을 갱신한다.

   - Why? 오늘 이후 최대 이익을 낼 수 있는 날에 판매하기 위해

   - 시간 복잡도 : O(N)

3. 구한 최대 이익 값을 결과로 출력한다.

 

 

💥 유의사항

- 앞에서부터 순방향으로 순회하며 구한다면, 시간 복잡도는 O(N^2)이고 시간 초과가 뜬다..

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        StringBuilder sb = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        for(int i = 0 ; i < T ; i++) {
            int N = Integer.parseInt(br.readLine());
            
            int[] arr = new int[N]; // 주식 시세 정보 저장용 배열
            
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
            }
            
            long answer = 0;  // 최대 이익 값
            long max = 0;
            
            // 주식 정보 역방향으로 탐색
            for(int j = arr.length - 1 ; j >= 0 ; j--) {
                if(arr[j] <= max)
                    answer += max - arr[j]; // 가장 비싸게 팔 수 있는 날 판매
                else
                    max = arr[j];   // 최대 이익 값 갱신
            }
            
            // 구한 최대 이익 값 결과로 출력하기
            sb.append(answer).append("\n");
        }
        
        System.out.println(sb.toString());
    }
}

 

 

---

💦 어려웠던 점

- 문제 자체를 이해하지 못 했다..ㄴㅇㄱ

 

 

🧐 새로 알게 된 내용

- 뒤에서부터 역방향으로 탐색하며 정답을 구하는 것이 포인트,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 그림 설명 덕분에 이해가 잘 되었다... 감사를....

[백준] 알고리즘 분류(그리디 알고리즘,JAVA)11501번, 주식

 

[백준] 11501 주식 - 우선순위큐 JAVA