[C++ 풀이] Codility - Lessons 6, (Sorting) Triangle

이 문제는 Codility 사이트에서 확인하고 문제를 풀 수 있습니다.

https://www.codility.com/

 

 

 

문제.

 

 

설명

 

A[] 배열이 주어지고 A의 범위는 0 ~ 100,000.

A배열의 각 원소의 값은 −2,147,483,648 ~ 2,147,483,647.

A배열의 원소중 다음의 조건식을 만족하는 결과를 구하시오.

 

A[P] + A[Q] > A[R],

A[Q] + A[R] > A[P],

A[R] + A[P] > A[Q].

 

 0 ≤ P < Q < R < N

 

 

위 예제인 

  A[0] = 10    A[1] = 2    A[2] = 5

  A[3] = 1      A[4] = 8    A[5] = 20

 

이걸 보면 알 수 있습니다.

 

해당 조건을 만족하는 배열 원소는 

 

A[0] = 10, 

A[2] = 5, 

A[4] = 8 입니다.

 

 

배열 원소들 중 해당 조건을 만족하는 값들이 존재 한다면 '1'을 반환,

그렇지 않으면 '0'을 반환하시면 됩니다.

 

 

 

 

결과

 

 

 

// you can use includes, for example:
#include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    if(A.size() < 2 || A.empty())
        return 0;
    
    sort(A.begin(), A.end());
    
    for(int i = A.size() - 1; i - 2 >= 0; i--){
        long n1 = A.at(i), n2 = A.at(i - 1), n3 = A.at(i - 2);
        if(n1 < n2 + n3)
            return 1;
    }
    
    return 0;
}
​

 

 

저 짧은 코딩을 할려고 4시간을 해맸습니다.(지금 맨붕...)

 

처음엔 그냥 막 쓰다가 계속 막히길래 곰곰히 생각해보니 규칙이 하나 보이더군요.

 

 

( P < Q < R )

여기서 P + Q > R 보다 크다면 나머지 조건을 모두 만족시키는 겁니다.

 

즉, P + Q > R 조건이 최소 조건이라는 뜻입니다.

 

R을 가장 큰 값으로 놓고, 그 다음 큰 두수의 합과 비교한 후,

조건이 성립하지 않으면 그 다음 큰수로 넘어가면 됩니다.

 

그리고 정수의 범위가 −2,147,483,648 ~ 2,147,483,647 이여서 int로 하기엔 부족합니다.

때문에 더한 후 비교할 때는 long변수를 사용해야 합니다.

 

 

 

아...... 현타온다..... 내 네시간....