swea 1859. 백만장자 프로젝트

문제 swea1859. 백만 장자 프로젝트

많은 유형의 문제를 접해야겠다고 생각했고, 안풀리는 문제를 하루종일 잡을 것도 아니라고 생각했다. 많은 유형을 풀어보고 이후에 안풀리는 문제를 잡아봐야지.

이렇게 생각한 이유는 간단한 문제인데 생쇼를 했다. 투포인터로 풀려고 하였는데 단순 그리디였다.

넘겨도 되는 내 잘못된 접근

앞에서부터 가장 큰 값 Max를 찾고, 그 이후의 배열에서 Max를 찾아서 빼줘야할 것 같다고 생각했다. 이 문제에서 계속 생각했던 부분은 앞에서부터이다.

시간복잡도상 N이 백만이기때문에 이중for문을 도는 행위는 절대하면 안된다.

그래서 가장 최근 풀었던 투포인터로 풀어야하나 생각했던 것 같다.

풀이

내가 고집했던 앞에서부터를 뒤집으면 되는 문제였다. 뒤에서부터 가장 뒤에 있는 값을 Max로 두고, 배열을 거꾸로 지나오면서 큰값이 있으면 Max를 갱신해주고, Max보다 값이 작으면 sum += Max - price[i] 해주면 된다.

왜냐하면 배열의 앞에서부터 가장 큰 값이 나올때 앞에 있는 모든 값들을 빼주면 되는데, 이를 뒤에서부터하면 price[i]가 price[i+1] 즉 현재 Max보다 작으면 값을 빼주는게 바로 순이익이 될 것이기 때문이다.
반면 price[i]가 Max보다 크면 price[i] 이후에 있는 값들은 쓸모가 없다.

풀이 코드 python

T = int(input())

for test_case in range(1, T+1):

    n = int(input())
    price = list(map(int, input().split()))

    sum = 0
    max = price[n-1] # 마지막 인덱스의 값을 최대값으로 설정하면서 구해나간다.

    for i in range(n-2, -1, -1):
        if price[i] < max:
            sum += max-price[i]
        else:
            max = price[i]

    print("#{} {}".format(test_case, sum)) 

풀이 코드 java

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

public class swea1859 {
    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 + 1; t++) {
            int n = Integer.parseInt(br.readLine());
            StringTokenizer stk = new StringTokenizer(br.readLine());

            int[] price = new int[n];
            for (int i = 0; i < n; i++) {
                price[i] = Integer.parseInt(stk.nextToken());
            }

            int maxPrice = price[n - 1];
            long sum = 0;

            for (int i = n - 2; i >= 0; i--) {
                if (price[i] < maxPrice) {
                    sum += maxPrice - price[i];
                }
                else {
                    maxPrice = price[i];
                }
            }

            System.out.printf("#%d %d\n",t,sum);
        }
    }
}