MaxProfit (Codility) - Java

문제

N개의 정수를 담는 배열 A가 주어진다. 0 <= P <= Q < N 조건을 만족하는 P, Q 중에서 A[Q] - A[P]가 가장 큰 값을 리턴하는 문제이다. 만약 값을 구할 수 없거나 가장 큰 값이 음수라면 0을 리턴한다.

 

해결 방법

쉽게 풀 수 있는 문제였다. 모든 A[Q] - A[P] 값 을컨테이너에 담아 정렬해볼까 하는 생각도 해봤지만 오히려 더 복잡해져 독이 되었다. (물론 시간 복잡도도 최악)

 

0 <= P <= Q < N를 만족하는 가장 작은 값과 가장 큰 값을 찾아 서로 빼주면 된다. min의 변수 값을 선언해 A[0]으로 초기화 시켜준다. 그 다음 순차적으로 A 배열을 순회하며 min 보다 작은 값을 찾으면 min 값을 갱신하는 동시에 현재 A의 인덱스 위치 값과 min을 빼준 값을 result라는 변수에 기록해 놓는다. 매번 뺄셈을 한 값이 result 값보다 크면 갱신한다. result를 0으로 초기화 했기 때문에 뺀 결과 값이 음수가 나오면 갱신하지 않는다. 

 

주의 할 점이 있는데 A가 비어 있는 경우이다. 이때 인덱스 접근을 하면 IndexOutofBoundException이 일어나므로 알맞은 예외처리를 해줘야 한다.

 

코드는 다음과 같다.

class Solution {
	public int solution(int[] A) {
		int min = (A.length > 0) ? A[0] : 0;
		int result = 0;
		for(int num : A) {
			if(num <= min) {
				min = num;
			}
			if(result < num - min) {
				result = num - min;
			}
		}
		return result;
	}
}