[백준] 11501번 : 주식 - 자바(Java)

Problem 🔒

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

0
10
5

예제 입력 2

1
10
1 2 7 1 2 1 3 5 4 3

예제 출력 2

24

예제 입력 3

1
9
8 5 3 8 10 7 5 5 2

예제 출력 3

16

---

Approach 1 ⭕

1. 뒤에서부터 주가 탐색
   • 뒤에서부터 주식을 탐색하며, 가장 높은 주식 가격을 찾아 팔 위치를 결정한다.
   • max 변수는 현재까지 본 주식 중 가장 높은 가격을 저장한다.
   • 주식 가격이 이전 주식보다 크거나 같고, max보다 큰 경우 해당 주식은 팔기 좋은 시점으로 간주하고 list에 해당 인덱스를 저장한다. 그리고 max 값도 갱신한다.
   • 그러면 list에는 주식을 팔 시점의 인덱스가 내림차순으로 저장된다.
2. 최대 이익 계산
   • 최종적으로 얻을 수 있는 최대 이익 변수는 long 타입으로 선언한다.
   • list의 뒤에서부터 인덱스를 꺼내 주식 배열을 처음부터 탐색한다.
   • list에서 꺼낸 인덱스에 저장된 주식 가격과 배열의 차이를 계산하여 ans에 저장한다. 이 때, 차이가 음수이면 ans에 더하지 않는다.
   • 배열의 인덱스(i)가 list에서 꺼낸 인덱스(idx)와 같아지면, list에서 다음 인덱스를 꺼낸다.

Approach 2 ⭕ - 더 직관적이고 간단하게

1. 최대 이익 계산
   • 주식 가격을 뒤에서부터 탐색하는 것은 동일하다.
   • 판매 시점에서 가장 높은 가격을 찾아 max에 저장한다.
   • 주식 가격이 max보다 크면, 새로운 판매 시점이 되어 max를 갱신하고, 그렇지 않으면 max에서 현재 주식 가격을 빼서 이익을 계산한다.
   • 이 풀이는 음수 이익을 따로 처리하지 않고, 무시할 수 있는 방식이다.
   • 그리고 list를 사용하지 않고, 간단하게 최대 이익을 구할 수 있다.

Learned 😯

1. 당장 주식 가격이 올라서 매도 시점으로 보이지만, 뒤에 더 큰 수익이 나는 매도 시점이 있을 수 있었다.
2. 답이 64bit로 표현가능해 최대 이익은 long 타입으로 선언해야했다.
3. list를 사용하지 않고, 매도 시점을 갱신하여 더 간단하게 구현이 가능했다.

---

Solution 💡

public class 그리디 {
    static int T, N, num[];
    static ArrayList<Integer> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        while(T-->0){
            N = Integer.parseInt(br.readLine());
            num = new int[N];
            list.clear();
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0; i<N; i++){
                num[i] = Integer.parseInt(st.nextToken());
            }
            // 뒤에서 부터 탐색하여 가장 높은 주가를 찾는다.
            int max = 0;
            for(int i=N-1; i>0; i--){
                if(num[i]>=num[i-1] && num[i]>max){
                    list.add(i);
                    max = num[i];
                }
            }
            long ans = 0; // 최대 이익이 int 범위를 벗어날 수 있다.
            int size = list.size();
            int idx = 0;
            for(int i=0, j=size-1; i<N; i++){
                if(j<0) break;
                idx = list.get(j);
                if(i==idx){j--; continue;}
                // 이익이 음수가 되면 더하지 않는다. (4% 틀렸습니다 해결)
                ans += Math.max((num[idx] - num[i]), 0);
            }
            sb.append(ans).append("\\n");
        }// while
        System.out.println(sb);
    }
}

더 간단하게

public class 그리디 {
    static int T, N, num[];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        while(T-->0){
            N = Integer.parseInt(br.readLine());
            num = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0; i<N; i++){
                num[i] = Integer.parseInt(st.nextToken());
            }
            int max = 0;
            long ans = 0;
            for(int i=N-1; i>=0; i--){
                if(num[i]>max) max = num[i];
                else ans += max-num[i];
            }
            sb.append(ans).append("\\n");
        }// while
        System.out.println(sb);
    }
}