[알고리즘] Valid Triangle Number

포인트

• 규칙을 만족하기 위한 세 수 갯수를 세는 문제 해결 입니다. 일반적인 해결 방법은 for loop 를 3번만 한다면, 해결할 수 있는 조건 입니다. 하지만, 이 경우 시간 초과를 경험할 수 있습니다. 
• 이를 해결하기 위해서는 다른 방법으로 접근을 해야 하는데 이를 해결할 수 있는 것이 투 포인터 알고리즘 입니다.
• 이 문제와 접근 방식의 문제인 3sum 도 확인하시면 좋을 것 같습니다.
  
  https://leetcode.com/problems/valid-triangle-number/

Valid Triangle Number - LeetCode

https://leetcode.com/problems/3sum/

3Sum - LeetCode

 

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        cnt = 0
        for i in range(len(nums)-1, 0, -1):
            left = 0
            right = i-1
            while left < right:
                if nums[right]+nums[left] > nums[i]:
                    cnt += right-left
                    right -= 1
                else:
                    left += 1
        else:
            return cnt