[Leetcode][611] Valid Triangle Number

문제 : https://leetcode.com/problems/valid-triangle-number/

---

0이상의 정수배열 nums가 주어질 때, 이 들 중 3개 수를 골라서 삼각형을 만들 수 있는 경우의 수를 구해라.

---

투포인터로 풀었다.

nums 배열을 오름차순 정렬한다.

nums를 처음부터 탐색하면서 탐색하는 정수는 고정적으로 사용하는 변의 길이다. (let, a)

탐색한 정수의 바로 다음 정수들을 탐색하는데 이를 다음으로 선택하는 변의 길이이다. (let, b)

삼각형을 만들기위한 2개의 변을 고정했다.

삼각형이 되기 위한 조건은 두 개의 변의 길이 합이 나머지 하나(최장길이 변)의 길이보다 커야한다.

나머지 변을 c라고 하자. 만일 이전 탐색으로 구한 길이들의 관계가 a + b > c 였다면, b는 탐색하면서 같거나 점점 커질 것이기 때문에, 앞으로 탐색될 b'에서도 a + b' > c 가 보장된다. (b는 num[i]라면 b'는 nums[i+x](x는 양수)이고 nums 배열은 오름차순 정렬되어있기때문. b < b')

즉, a + b <= c (삼각형이되지 못하는 경우)가 되는 c 변의 nums 인덱스를 구하고 b가 업데이트 될 때, c도 a + b <= c 조건에 맞게 갱신시킨다.

투포인터 관점에서보면 b가 되는 nums 인덱스를 left, c가 되는 nums 인덱스를 right로 볼 수 있다.

right 인덱스는 정답이 될 수 없고 c는 left + 1 부터 시작하기 때문에 (left + 1) ~ (right - 1) 까지가 정답이 가능한 경우이므로, 이들을 탐색하며 right - left + 1들의 합을 구하면 정답이 된다.

 

시간복잡도는 nums 배열 길이를 N이라 했을때, 투포인터 탐색하며 드는 시간인 O(N^2) + 정렬하는데 드는 시간인 O(NlogN) 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/611.%20Valid%20Triangle%20Number.cpp