[Baekjoon] 백준 11501 주식 (S1 / 그리디) - Java

링크

https://www.acmicpc.net/problem/11501

11501번: 주식

 

 

 

 

문제 해석

날짜별 주가 제공
하루에 주식은 최대 하나를 살 수 있음
주식을 통해 얻을 수 있는 최대 이익 찾기


- 입력
첫 번째 줄 : N
  N : 일수
두 번째 줄 :  날 별 주가


- 출력
각 테스트 케이스별 최대 이익을 개행을 통해서 출력

 

 

 

 

풀이 & 코드 해석

해당 문제는 단순하게 생각해보면

차례대로 자신 이후에 나오는 최대값에서 자신을 뺀 값을 구하고,

구해진 모든 값을 더하면

정답을 찾을 수 있습니다.

 

다만 N이 최대 1,000,000이기 때문에 시간 초과가 날 가능성이 있습니다.

 

이 문제는 풀이 시 탐색하는 방향을 역으로 진행한다면 쉽게 풀 수 있습니다.

 

 

 

ex) 1 2 3 4 3 1

 

가령 위와 같은 식이 있다고 가정할 때,

순차적으로 실행하면 가장 앞에 있는 수 1은 자신보다 큰 수가 있는지 찾기 위해서 가장 마지막에 위치한 1까지 탐색해야 합니다.

 

 

하지만 반대로 탐색하는 경우 가장 마지막에 값을 최대 값으로 가정하고 탐색해 나간다면,

비교대상인 숫자가 최대 값보다 큰 경우 탐색할 필요 없이 사더라도 이익이 없을 것을 알 수 있습니다.

이럴 때는 단순히 최대 값을 비교 대상 숫자로 업데이트만 시켜주면 됩니다.

(뒤에서부터 시작 시, 현재 1이 최대이고, 다음 값인 3은 최대인 값 1보다 크기 때문에 사더라도 이득을 볼 수 없음)

 

한편 비교대상 숫자가 최대 값보다 작은 경우 구매하면 최대값-비교값 만큼 이득을 볼 수 있습니다.

(최대값이 4이고 다음 비교값이 3이라면 주식 구매시 1만큼의 이득을 볼 수 있음)

 

 

 

 

코드

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

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

        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());

        for (int test_case = 0; test_case < T; test_case++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());

            int[] arr = new int[N];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            long answer = 0;
            int max = 0;

            for (int i = N - 1; i >= 0; i--) {
                if (max < arr[i]) {
                    max = arr[i];
                } else if (max > arr[i]) {
                    answer += max - arr[i];
                }
            }
            System.out.println(answer);
        } // [E] test_case
    } // [E] main
}

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java