[Codility] Lesson6. Sorting-Triangle C언어 풀이

1. 문제

길이가 N인 배열 A가 주어졌을 때, 삼각형이 이루어지는지 확인하는 문제

삼각형이 되기 위한 조건

$0≤P<Q<R<N$
A[P] + A[Q] > A[R]
A[Q] + A[R] > A[P]
A[R] + A[P] > A[Q]

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

(0, 2, 4)가 조건에 일치하므로 1을 반환해준다.

2. 정답

첫번째 - 100점

$O(N*log(N))$ or $O(N)$

void swap(int* data, int index1, int index2)
{
    int temp = data[index1];
    data[index1] = data[index2];
    data[index2] = temp;
}

void quickSort(int* data, int left, int right) 
{
    int pivotValue = data[(left + right) / 2];
    int i = left;
    int j = right;

    while (i <= j)
    {
        while (data[i] < pivotValue) i++;
        while (data[j] > pivotValue) j--;
        if (i <= j)
        {
            swap(data, i, j);
            i++;
            j--;
        }
    }
    if (left < j)
        quickSort(data, left, j);    
    if (right > i)
        quickSort(data, i, right);    
}

int solution(int A[], int N) {
    quickSort(A , 0, N-1);
    
    for(int i = 0; i < N-2; i++){
        if(A[i] > A[i+2] - A[i+1])
            return 1;
    }
    return 0;
}

조건이 3개인 것 같지만 가장 작은 2개의 합이 가장 큰 수보다 크면 나머지 2개의 조건도 성립하게 되어있다.
정렬되어있다면 A[0] < A[1] < A[2] 식이 참이 된다. 여기서 A[0] + A[1] > A[2] 조건이 성립되면 1을 반환해주면 된다.
하지만 여기서 A[0]와 A[1]의 합이 int의 범위를 넘어가면 오류가 발생하므로, A[0] > A[2] - A[1] 또는 A[1] > A[2] - A[0]로 조건으로 변경해 주어야 한다.