[코딩테스트] 백만 장자 프로젝트 | SWEA

문제

✏️ 문제 바로가기

제목	레벨	정답률
백만 장자 프로젝트	D2	32.92%

최적화 코드

import java.util.*;

class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++){
            int n = sc.nextInt();
            int[] prices = new int[n];
            for(int i = 0; i < n; i++){
                prices[i] = sc.nextInt();
            }

            long profit = 0; // 이익을 long 타입으로 선언하여 오버플로우를 방지합니다.
            int maxPrice = 0; // 최대 가격을 저장하기 위한 변수
            for(int i = n - 1; i >= 0; i--){ // 가장 마지막 날부터 역순으로 탐색
                if(prices[i] >= maxPrice){ // 현재 가격이 최대 가격보다 크거나 같으면
                    maxPrice = prices[i]; // 최대 가격 갱신
                } else { // 현재 가격이 최대 가격보다 작으면
                    profit += maxPrice - prices[i]; // 최대 가격에서 현재 가격을 빼서 이익에 더합니다.
                }
            }

            System.out.println("#" + test_case + " " + profit);
        }
    }
}

우선 결론적으로, 나는 이 문제를 풀지 못했다.
나는 배열을 앞에서부터 순차적으로 탐색해나가면서 다음에 오는 가격이 현재 가격보다 크면 계속 구매하고, 다음에 올 값이 작은 값이면 팔아버리는 식으로 구현했었다.

이렇게 하면 예시로 나온 3가지 케이스는 통과가 되었다. 그런데 제출을하니 실패가 떴다.
이런 경우는 보통 예외 상황을 고려하지 못한 경우이다.
그래서 AI의 도움을 받았는데 포인트는 바로 역순으로 탐색하는 것..!

순차적으로 탐색해나가면 정확한 이익을 계산할 수 없는 경우가 생길 수 있다고 한다.
그래서 거꾸로 탐색을 해나가면서, 현재 가격보다 큰 가격이 나올때까지 최대 가격을 계속해서 갱신한다. 그리고 최대 가격보다 작은 값이 나오면 최대 가격에서 현재 가격을 뺀값을 이익에 더해나간다.

---

이번 문제는 코드를 짜기 전에 풀어나가는 방법부터 감을 못잡은 케이스인데, 이런 경우는 오랜만이라 신선했다.
D2 레벨에 비해 정답률도 낮고 난이도도 높은 것 같아 좀 의외였다. 그렇지만 비슷한 문제가 나오면 무조건 맞출 수 있을 것 같아서 아주 유익한 시간이었다 :-)