https://app.codility.com/demo/results/training7PAXM8-RG2/

문제

An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

A[P] + A[Q] > A[R],
A[Q] + A[R] > A[P],
A[R] + A[P] > A[Q].
For example, consider array A such that:

A[0] = 10 A[1] = 2 A[2] = 5
A[3] = 1 A[4] = 8 A[5] = 20
Triplet (0, 2, 4) is triangular.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

For example, given array A such that:

A[0] = 10 A[1] = 2 A[2] = 5
A[3] = 1 A[4] = 8 A[5] = 20
the function should return 1, as explained above. Given array A such that:

A[0] = 10 A[1] = 50 A[2] = 5
A[3] = 1
the function should return 0.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

코드

// 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");
import java.util.*;
class Solution {
    public int solution(int[] A) {
        int ans = 0;
        if(A.length == 0){
            return 0;
        }
        Arrays.sort(A);
        for(int i=A.length-1; i>=2; i--){
            if(A[i] < A[i-1]+A[i-2])
            { 
              return 1;
            }
        }

        return ans;
    }
# }

풀이

8+5>10 성립시, 10+8>5와 10+5>8은 무조건 성립
즉, 가장 큰 수를 기준으로 나머지 수를 더했을 때 가장 큰 수보다 더 큰지만 체크하면 된다.
그런데 이때,아래와 같은 오류가 발생한다.
extreme_arith_overflow1
overflow test, 3 MAXINTs✘WRONG ANSWER
got 0 expected 1
1.0.004 sWRONG ANSWER, got 0 expected 1

이 에러 메시지는 주어진 테스트 케이스에서 오버플로우 문제가 발생했음을 나타내는데, 테스트 케이스의 이름인 extreme_arith_overflow1에서도 알 수 있듯이, 이 테스트는 특히 큰 숫자인 MAXINT에 대한 오버플로우를 테스트하고 있다.

Java에서 MAXINT는 Integer.MAX_VALUE로, 값은 2,147,483,647이다.

오버플로우는 컴퓨터에서 숫자를 표현하는 범위를 초과할 때 발생하는 현상으로, 이 경우, A[i-1] + A[i-2]의 계산에서 오버플로우가 발생했을 가능성이 있다.

A[i-1]와 A[i-2]가 모두 MAXINT인 경우, 두 수를 더하면 결과는 2 * MAXINT가 되므로 int의 최대 표현 범위를 초과하게 된다.

이 문제를 해결하려면 long 형을 사용하여 덧셈을 수행하고, 이렇게 하면 덧셈 결과가 int의 최대 범위를 초과하더라도 오버플로우가 발생하지 않는다.

java
Copy code
import java.util.*;
class Solution {
    public int solution(int[] A) {
    
    Arrays.sort(A);
    int n = A.length-1;
    for(int i=n; i>=2; i--){
        if((long)A[i] < (long)A[i-1] + (long)A[i-2]){
            return 1;
        }
    }

    return 0;
    }
}

이렇게 수정하면, A[i-1]와 A[i-2]를 더할 때 int 범위를 초과하는 오버플로우 문제를 방지할 수 있다.