MaxProductOfThree
Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).
Task Score
100%
Correctness
100%
Performance
100%
다시 painless레벨로 오니까 마음이 편해진다.. 자꾸 쉬운거만 하려구 하면 안되지만 ㅠㅠㅠ
단순하게 생각하면 세개를 뽑아 최대값을 구해야하니까 맨 위 세개만 뽑아 곱하면 된다.
라고 생각할 수 있지만, 만약 음수나 0값이 포함돼있다면 어떨까?
정렬 후 A = {-100, -1, 0, 1, 2} 가 된다면, 이런 방식으로 구했다가는 0이 나오게 된다. (-100 * -1 * 2) = 200이라는 큰 값을 구할 수 있는데 말이다.
그래서 음수나 0이 두개 이상이고 마지막 값은 양수인 경우는 첫 값, 두번째 값, 마지막 값을 곱해 마지막 세개를 곱한 경우와 비교해준다. 예를 들어 A = {-10, -1, 1, 2, 100} 이면 answer = 200, answer2 = 1000이므로 answer를 answer2의 값으로 치환해 반환해주고, A = {-2, -1, 2, 3, 4}인 경우 answer = 24, answer2 = 8이므로 answer2의 값을 무시하고 바로 answer의 값을 반환해준다.
xxxxxxxxxx
// 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) {
Arrays.sort(A);
int i = A.length - 1;
int answer = A[i] * A[i - 1] * A[i - 2];
if (A[0] <= 0 && A[1] <= 0 && A[i] >= 0) {
int answer2 = A[0] * A[1] * A[i];
if (answer2 > answer) answer = answer2;
}
return answer;
}
}
'공부 > algorithm' 카테고리의 다른 글
[programmers] 올바른 괄호 (0) | 2018.06.05 |
---|---|
[programmers] 같은 숫자는 싫어요 (0) | 2018.06.05 |
[codility] MinAvgTwoSlice (0) | 2018.05.24 |
[codility] GenomicRangeQuery (0) | 2018.05.24 |
[codility] PassingCars (0) | 2018.05.23 |
댓글