[Leet Code] 611

LeetCode 611. Valid Triangle Number

문제 링크

---

📝 문제 해석

정수 배열 nums가 주어졌을 때, 배열에서 세 개의 수를 골라 삼각형의 세 변으로 만들 수 있는 경우의 수를 구하는 문제입니다.

삼각형의 조건은 삼각 부등식에 따라 가장 긴 변을 c라 할 때,
a + b > c 가 반드시 성립해야 합니다.

💡 접근 방법

1. 브루트포스 (O(n³))
   • 세 개의 수를 전부 조합으로 골라 확인 → 배열 길이가 커지면 시간 초과
2. 정렬 + 투 포인터 (O(n²))
   • 배열을 오름차순 정렬
   • 가장 긴 변 nums[k]를 고정하고, 나머지 두 변을 투 포인터로 탐색
   • 만약 nums[i] + nums[j] > nums[k]라면, i..j-1까지 모두 성립 → 한 번에 카운트

🧑‍💻 코드 (Python)

# Ex 1)
nums = [2,2,3,4]  # Output: 3

from typing import List

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        # 오름차순 정렬
        nums.sort()
        answer = 0

        # 삼각형 조건 : a + b > c
        for k in range(len(nums) - 1, 1, -1):
            i, j = 0, k - 1
            while i < j:
                if nums[i] + nums[j] > nums[k]:
                    answer += j - i
                    j -= 1
                else:
                    i += 1
        return answer
        
        

S = Solution()
print(S.triangleNumber(nums))