Lesson 6. Sorting - Triangle #1

1. 문제

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:
  int solution(vector<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].

 

삼각형을 만들 수 있는지 판단하는 문제.

삼각형 조건은 다음과 같다.

1. 0 \( \leq \) P < Q < R < N
2. A[P] + A[Q] > A[R]
3. A[Q] + A[R] > A[P]
4. A[R] + A[P] > A[Q]

 

예시1) return 1 ( 삼각형 만들 수 있음, A[0], A[2], A[4] )

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]
10	2	5	1	8	20

 

예시2) return 0 (삼각형 만들 수 없음)

A[0]	A[1]	A[2]	A[3]
10	50	5	1

 

2. 매개변수 조건

1. Vector A 크기(N): 0 ~ 100,000
2. Vector A 요소 값 범위: -2,147,483,648 ~ 2,147,483,647

 

3. 코드 (C++)

int 최대값(4byte)이 있을 경우, 정수 오버플로우가 발생한다.

따라서 8byte 정수형을 다룰 수 있는 int64_t type을 사용했다. (cstdint 참고)

#include <cstdint>

int solution(vector<int> &A) {

    for(size_t P = 0; P < A.size(); P++)
    {
        int64_t p = A[P];
        for(size_t Q = P + 1; Q < A.size(); Q++)
        {
            int64_t q = A[Q];
            for(size_t R = Q + 1; R < A.size(); R++)
            {
                int64_t r = A[R];
                if(p < q + r)
                {
                    if(q < r + p)
                    {
                        if(r < p + q) return 1;
                    }
                }
            }
        }
    }

    return 0;
}

 

4. 결과