LeetCode (C/C++) 611. Valid Triangle Number

https://leetcode.com/problems/valid-triangle-number/description/

---

풀이

삼각형의 조건은 가장 큰 변의 길이가 나머지 두 변의 길이보다 작아야 한다.

이를 위해 주어진 문자열을 오름차순으로 정렬한 후, 두 변을 기준으로 탐색했다.

두 변의 길이의 합 보다 작은 수의 위치를 찾고, 해당 수의 위치보다 작은 값들 중 나머지 두 변의 위치가 아닌 수의 개수를 더했다.

---

코드

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;

        int size = nums.size();
        for (int i = 0; i < size - 2; i++) {
            for (int j = i + 1; j < size - 1; j++) {
                int sum = nums[i] + nums[j];

                // i + j < k인 k의 위치 찾기
                int maxIdx = lower_bound(nums.begin(), nums.end(), sum) - nums.begin();
                
                // k 보다 작거나 같은 값 중 j 보다 뒤에 위치한 수의 개수 더하기
                ans += max((maxIdx - j - 1), 0);
            }
        }
        return ans;
    }
};