[백준 #11501] 주식

백준 #11501 주식

백준 #11501

---

문제 설명👩‍🏫

날 별로 주가를 보고 주식을 사거나, 팔거나, 아무것도 하지 않을 때, 최대 이익을 낸다면 얼마일지 구해라.

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

입출력 예

입력
3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

출력
0
10
5

---

내 코드💻

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int testCases = Integer.parseInt(str);
        long sum=0;

        for(int t=0;t<testCases;t++){
            sum = 0;
            str = br.readLine();
            int day = Integer.parseInt(str);
            int []date = new int[day];

            str = br.readLine();
            StringTokenizer st = new StringTokenizer(str, " ");

            for(int d=0;d<day;d++){
                date[d] = Integer.parseInt(st.nextToken());
            }
            
            int max = date[day-1];
            for(int i=day-2;i>=0;i--){
                if(date[i]<=max){
                    sum += max-date[i];
                }
                else if(date[i]>max){
                    max = date[i];
                }
            }

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

---

설명💡

주가를 날별로 입력받고, 가장 뒤에 날을 max로 잡는다.
그리고 앞으로 날을 옮기면서 주가를 비교한다. max보다 작다면 그 차이는 즉 이익이 된다는 뜻이므로 sum에 추가한다.
max보다 큰 값이 나타난다면, max를 큰 값으로 변경해주고 위를 반복한다.

---

실패한 코드(1차 시도)😟

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int testCases = Integer.parseInt(str);
        int sum=0;

        for(int t=0;t<testCases;t++){
            sum = 0;
            str = br.readLine();
            int day = Integer.parseInt(str);
            int []date = new int[day];

            str = br.readLine();
            StringTokenizer st = new StringTokenizer(str, " ");

            for(int d=0;d<day;d++){
                date[d] = Integer.parseInt(st.nextToken());
            }

            ArrayList<Integer> list = new ArrayList<>();
            
            for(int i=0;i<day;i++){
                list.add(date[i]);
                if( i==day-1||(i<day-1 && date[i]>date[i+1])){
                    for(int j=0;j<list.size();j++){
                        sum += date[i]-list.get(j);
                    }
                    list = new ArrayList<>();
                }
            }
            
            System.out.println(sum);
        }
    }
}

처음에 내가 적은 코드는 테스트 케이스가 운좋게 맞은 부분이었고, 정확히 문제를 풀어내기 위해서는 뒤에서부터 확인해야한다.

1
6
5 3 1 6 2 7
이 경우일 때 위의 코드로 진행하면,
6-1 + 6-3 + 6-5 + 7-2 = 14 가 나오지만,

정답은
7-2 + 7-6 + 7-1 + 7-3 + 7-5 = 18 이 나와야한다.

6보다 더 큰 값인 7을 간과한 코드가 되버린다.

---

실수한 부분😟

int sum=0;

출력 조건에 답은 부호있는 64bit 정수형으로 표현 가능하다. 는 말을 간과했다.. int가 아닌 long으로 했어야했다..

---

느낀 점 및 궁금한 점🍀

그리디 알고리즘.. 아직 생각하는 게 너무 어렵다.. 뒤에서부터 하는 건 떠올리기에 아직 익숙하지가 않은 것 같다..