⏹️[SW Expert Academy] [Python] [D2] [1859] 백만 장자 프로젝트

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&problemLevel=3&problemLevel=4&problemLevel=5&contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=5&pageSize=10&pageIndex=1

SW Expert Academy

풀이

처음 문제를 풀어본다면 조금 생각하는 방식을 달리해야해서 어려움이 있었을 것 같다. 나도 처음에 문제를 봤을 때 스택이나 큐를 이용해서 처리해보려고 했다. 주어진 조건을 잘 활용하면 해결할 수 있는 문제이다. 테스트 케이스의 첫번째는 10, 7, 6 으로 값이 점점 감소하므로 구매하지 않는 것이 최적의 해이다. 두번째는 값이 항상 증가하므로 그날 바로 사서 마지막 날에 팔면된다. 마지막 세번째 케이스만 경우의 수를 생각해주면 되는데 1, 1, 3, 1, 2 로 첫째와 둘째날에는 구매를해서 셋째날에 팔고, 넷째날에 사서 다섯째날에 팔면된다. 먼저 이 순서를 역으로 생각해보자. 그러면 2, 1, 3, 1, 1이 된다. 2->1로 갈때 팔고, 3->1로 갈때 팔고, 1->1로 갈때 3-1을 해주면 된다.  즉, 역으로 구성된 이전 값이 다음 값보다 크다면 팔고, max_val이라는 값에 가장 큰 값을 저장해 두도록한다. 

이것을 코드로 보자면 아래와 같다.

# 1859. 백만 장자 프로젝트 D2
T = int(input())
for test_case in range(1, T+1):
    N = int(input())
    price = list(map(int, input().split()))
    price = price[::-1]
    length = len(price)
    max_val = price[0]
    result = 0

    for i in range(1, length):
        if max_val > price[i]:
            result += max_val - price[i]
        else:
            max_val = price[i]
    
    print("#{} {}".format(test_case, result))

1. price를 입력받고 뒤집어 준다.

2. max_val에는 처음 시작값을 넣어준다.

3. 인덱스는 1부터 마지막까지 for문을 돌아준다.

- 만약 max_val이 가격보다 비싸다면 물건을 팔 것이기 때문에 결과에 더해준다.

- max_val이 가격보다 싸거나 같다면 max_val의 값을 최댓값으로 변경해준다. 

 

Java 코드

package SWEA;

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

public class SW_1859 {
    public static void main(String[] args) throws Exception, NullPointerException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for(int test_case = 1; test_case <= T; test_case++)
        {
            int N = Integer.parseInt(br.readLine());
            int[] price = new int[N];
            st = new StringTokenizer(br.readLine(), " ");
            for(int i=0; st.hasMoreTokens(); i++){
                price[i] = Integer.parseInt(st.nextToken());
            }
            int length = price.length;
            int maxValue = price[N-1];
            long result = 0;

            for(int i=N-1; i>=0; i--){
                if(price[i] > maxValue) maxValue = price[i];
                result += maxValue-price[i];
            }
            System.out.println("#" + test_case + " " + result);
        }
    }
}

테스트 케이스 10개중 7개 맞았다고 해서 아무리 봐도 파이썬 코드랑 비교해보고 다른사람의 코드랑 비교해봤을 때 틀린게 없었는데 알고보니 result의 타입이 int형이었다. 100만 * 1만 했을 때 표현할 수 있는 int형 범위를 넘어가기 때문이다.

이런 것 때매 시간 낭비를 하는게 ..