Codility Lesson 09 - MaxProfit(JAVA)

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_profit/

MaxProfit coding task - Learn to Code - Codility

 

문제

- N개의 정수들로 이루어진 A배열이 있다.

- A배열은 N개의 연속된 기간동안 일일 주가를 포함합니다.

- 0 ≤ P ≤ Q < N 범위에서 P는 주식을 매수하고 Q에서 매도 했다고 했을 때, Profit(이익)은 A[Q] - A[P] 의미하며,

A[Q] ≥ A[P]일 때는 이익을 반대일 경우에는 A[P] - A[Q]가 손해를 의미합니다.

- 예시 : A[0] = 23171 A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367

  0 bought 2 sold : A[2] - A[0] = 23171 - 21123 = -2048( 2048만큼 손해 )

  4 bought 5 sold : A[5] - A[4] = 21367 - 21013 = 354( 354만큼 이익 )

  최대 이익은 356으로 1 bought 5 sold할 때이다. return 356

- 최대 이익을 구해라( 어떤 이익도 얻지 못할 때는 return 0 )

 

제한조건

• N is an integer within the range [0..400,000];
• each element of array A is an integer within the range [0..200,000].

N은 0 ~ 400,000 사이의 정수이다.

A 배열의 각각의 원소는 0 ~ 200,000 사이의 정수이다.

 

풀이

- A배열의 길이가 1이하일 때는 이익을 얻을 수 없으므로 예외처리

- int minValue( 배열중 최소값 ), int maxProfit( 최대이익 ) 변수를 초기화하고, A배열만큼 for문을 순회하며 로직을 실행한다.

- for문 순회시 로직

- A배열의 첫번째 값을 minPrice로 초기화, maxProfit = 0 초기화

- index = 1부터 실행하며, 해당 price - minPrice로 profit을 구하고 maxProfit과 비교하여 큰 수로 교체한다.

- maxProfit 비교 후 minPrice와 해당 price를 비교하여 작은 수로 교체한다.( P=Q의 경우에는 profit = 0, P<Q일 경우 profit이 발생 할 수 있기에 이런 로직이 사용 가능 )

 

예상 시간복잡도 : for문 모두 순회 - O(N)

 

소스코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int maxProfit = 0;

        if( A.length < 2 ) return maxProfit;

        int minPrice = A[0];

        for( int i=1; i<A.length; i++ ){
            int profit = A[i] - minPrice;
            maxProfit = profit > maxProfit?profit:maxProfit;
            minPrice = A[i] < minPrice?A[i]:minPrice;
        }

        return maxProfit;
    }
}

 

PS. 다른 분들은 어떻게 풀었나 검색하던 중( 이론은 전혀 모르고 생각나는대로 풀었다 보니.. )에 다이나믹 프로그래밍 중 카데인 알고리즘이라는 것이 있는 것을 찾아서 참고를 달아둠

https://sustainable-dev.tistory.com/22

Codility Lesson9 - MaxProfit