이 문제는 Codility 사이트에서 확인하고 문제를 풀 수 있습니다.
문제.
설명
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변수를 사용해야 합니다.
아...... 현타온다..... 내 네시간....
'코딩테스트 > Codility' 카테고리의 다른 글
[C++ 풀이] Codility - Lessons 7, (Stacks and Queues) Fish (0) | 2019.09.28 |
---|---|
[C++ 풀이] Codility - Lessons 7, (Stacks and Queues) Brackets (0) | 2019.09.22 |
[C++ 풀이] Codility - Lessons 6, (Sorting) Distinct (0) | 2019.08.18 |
[C++ 풀이] Codility - Lessons 6, (Sorting) MaxProductOfThree (0) | 2019.08.09 |
[C++ 풀이] Codility - Lessons 5, (Prefix Sums) CountDiv (0) | 2019.08.08 |
댓글