Triangle (Codility)

문제

N개의 배열 A에서 0<= P < Q < R < N을 만족하는 인덱스 위치 P, Q, R의 값들이 다음과 같은 식을 만족하는 경우 

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

1을 출력하고 모든 경우에서 위 조건을 만족하지 않는다면 0을 출력하면 되는 문제이다.

 

해결 방법

우선 위와 같은 방법을 직접 적용하여, 모든 인덱스 경우에서 조건을 만족할때까지 찾는 방법이 있다. 예를 들면 (0, 1, 2), (1, 2, 3), ..., (0, 2, 3), ..., (N - 3, N - 2, N - 1) 모든 경우의 인덱스를 검사하며 위 조건을 만족하는 것을 찾으면 바로 1을 리턴하는 것이다. 하지만 이 방법은 삼중 반복문을 사용하므로 시간복잡도가 O(N^3)이다. 즉 최대 10만개의 배열 크기를 처리하기에는 매우 비효율적인 알고리즘이다.

 

우선 이것을 해결하기 위해서는 정수를 담은 원소를 오름차순으로 정렬해야 한다. 그리고 정렬된 상태에서 인접한 3개의 인덱스 값들만 조건을 검사해주면 된다.

 

위 A 배열 예제를 예로들어 풀어보자. 우선 정렬하면 다음과 같다.

10  2  5  1  8  20

(정렬)

1  2  5  8  10  20

그리고 순서대로 검사한다.

1  2  5 8  10  20 => 1 + 2 > 5 (조건 X)
1  2  5  8 10  20 => 2 + 5 > 8 (조건 X)
1  2  5  8 10  20 => 5 + 8 > 10 (조건 O)

5 + 8 > 10 이 만족한다면, 나머지 조건들도 만족하게 되므로 따로 조건을 검사할 필요가 없다. 

 

하지만 여기서 잘못 생각할 수 있는 조건이 있는데 바로 0<= P < Q < R < N이다. 이것은 그저 P, Q, R이 중복이 아니라는 것을 설명하기 위한 조건으로 꼭 인덱스가 순서대로 와야한다는 뜻은 아니다. 

 

코드로 표현하면 다음과 같다.

 

주의할 점이 하나 더 있는데 더하면서 int 범위를 넘어갈 수 있는 문제이다. 그렇기 때문에 조건을 검사할때 long long으로 캐스팅해줘야 한다.

#include <algorithm>
int solution(vector<int>& A) {
	sort(A.begin(), A.end());
	for (int i = 2; i < A.size(); ++i) {
		if ((long long)A[i - 2] + A[i - 1] > (long long)A[i]) return 1;
	}
	return 0;
}