Codility - Triangle 문제풀이

Codility - Triangle

☞ 문제 링크

문제 설명

중복되지 않는 인덱스 3가지를 선택하고, 2가지 인덱스 값의 합이 나머지 1가지의 인덱스 값보다 모두 큰 경우가 존재하는지 찾는 문제입니다. 예제로 주어진 케이스는 A[0] = 10, A[2] = 5, A[4] = 8 인 경우인데,

• 10 + 5 > 8 (참) // A[P] + A[Q] > A[R]
• 5 + 8 > 10 (참) // A[Q] + A[R] > A[P]
• 8 + 10 > 5 (참) // A[R] + A[P] > A[Q]

세가지 경우가 문제에 내용을 만족하는 참입니다. 

이런 경우의 배열이라면 1을 반환하고, 아니라면 0을 반환해야 합니다.

풀이에 핵심은 배열을 정렬한 상태에서 인접한 세개의 인덱스간의 비교만 진행하면 됩니다.

(그리고 인덱스에 대한 대소조건을 보면, 인덱스를 고려해야 할 것 같지만, 실제로 인덱스는 중복되지만 않으면 괜찮습니다.) 

즉, 주어진 예제의 배열을 정리하면 1, 2, 5, 8, 10, 20으로 정렬되고, 인접한 세개의 인덱스간의 조건을 충족하는지 확인합니다.

다시 말해 비교해봐야 하는 경우는

1, 2, 5, 8, 10, 20

1, 2, 5, 8, 10, 20

1, 2, 5, 8, 10, 20

1, 2, 5, 8, 10, 20

와 같이 4가지 경우입니다.

그리고 4가지 경우에서 문제에 조건을 만족하는 경우는 1, 2, 5, 8, 10, 20가 있습니다.

그런데 이미 배열이 정렬되어 있기 때문에, 세가지 경우를 모두 확인하지 않고, 작은 인덱스 2개의 합과 나머지 큰 인덱스의 값만 비교하면 됩니다.

5 + 8 > 10 인 경우가 참이라면, 나머지 경우는 당연히 참일수 밖에 없습니다.

문제 풀이 (java)

class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);//배열의 요소들을 정렬해준다.
        int triangularCount = 0;

        for (int i = 0; i < A.length - 2; i++) {
            if (A[i] + A[i+1] > A[i + 2]) {//인접한 인덱스 3가지를 비교한다.
                return 1; //한가지 경우라도 만족하면 바로 1을 리턴한다.
            }
        }

        return 0;
    }
}

하지만 이런식으로 제출하게 되면, 한가지 경우에서 오답이 나오게됩니다. (띠용~!) 바로 두 가지의 합이 오버플로우가 발생하는 경우인데요. 예를 들어, 2,147,483,645 + 2,147,483,646 > 2,147,483,647를 만족하게 되지만, 실제 연산 결과는 오버플로우가 발생하게 됩니다! 알고리즘 문제를 풀면서 처음으로 오버플로우에 발목이 잡혀서 신선한 경험이었습니다. 간단히 수학적 수식의 변형을 이용해서 오버플로우가 발생되지 않도록 변경하였습니다.

class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);
        int triangularCount = 0;

        for (int i = 0; i < A.length - 2; i++) {
            if (A[i + 1] > A[i + 2] - A[i]) {//오버플로우가 발생하지 않도록 식을 변형
                return 1;
            }
        }

        return 0;
    }
}

배운점 (★★★★ 아주 배운게 많은 알고리즘 문제였다.)

1. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N(배열의 사이즈) 이라는 표현이 있었는데, 결국 중복되지 않는 인덱스의 값을 나타내는 식이였다. 괜히 인덱스에 대한 순서가 중요한 것은 아닌지 생각할 필요 없다.
2. 문제를 제대로 읽지 않고, 반환값을 만족하는 경우의 갯수로 생각해서 처음에 애를 좀 먹었다. 항상 문제를 추측하지 말고 끝까지 읽자. 디버깅 하는 시간이 더 오래걸린다.
3. 두개의 합을 진행 할 때, 오버플로우를 고려해야 한다는 사실을 배웠다. 아주 소중한 경험이다. 문제에 주어진 range를 잘 확인하고 합을 진행할 때, 오버플로우가 나지 않는지 생각하자.