백준 11501번 - 주식 (java)

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

11501번: 주식

 

💡 아이디어

• 처음에는 앞에서부터 확인하며 다음날 주가가 내려가면 무조건 매도(판다)하는 방향으로 코드를 작성하였다.
• 오답이 떠서 더 생각을 해보니 다음날 주가가 내려가더라도 그 이후의 날들 중에 오늘보다 주가가 높은 경우를 생각하면 계속 매수(산다)를 하는 것이 이득이었다.
• 그래서 최고가가 되기 전까지는 계속 매수를 하는 것이 최대 이익을 남길 수 있는 방법이라는 생각이 들었다.
• 최고가를 찍은 이후의 날들에서는 남은 날들 중 최고가를 찍는 날을 기준으로 생각하면 된다.
• 그래서 뒤에서부터 확인을 해야한다는 것을 깨달았다.
• 아래 2가지를 반복한다. 
  • 날 별 주가를 뒤에서부터 확인하며 최댓값이 갱신이 안됐으면 현재 최고가와의 차를 계산해 이익을 더한다.
  • 최고가를 갱신한다.
• 한 가지 주의할 점은, 문제에 '답은 부호있는 64bit 정수형으로 표현 가능합니다.' 라는 내용이 있기 때문에 최대 이익을 저장하는 변수는 long 타입으로 지정해야 한다.

 

💡 코드

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

public class BOJ_S2_11501_주식 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int t = 1; t <= T; t++) {
            long profit = 0; //이익
            int days = Integer.parseInt(br.readLine());
            int[] price = new int[days]; //날 별 주가
            int max = Integer.MIN_VALUE; //현재 최대 주가
            int[] buy = new int[days]; //날 별 매수 단가
            int num = 0; //매수한 주 수
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < days; i++) {
                price[i] = Integer.parseInt(st.nextToken()); //입력 받기
            }
            for (int i = days - 1; i >= 0; i--) { //뒤에서부터 확인
                if (price[i] > max) {
                    max = price[i]; //최댓값 갱신
                } else {
                    profit += (max - price[i]);
                }
            }
            System.out.println(profit);
        }
    }
}