[LeetCode] 611. Valid Triangle Number (Swift, Python)

Valid Triangle Number - LeetCode

 

풀이

 먼저 삼각형을 만들기 위해서는 가장 긴 변의 길이가 나머지 두 변의 합보다 작아야 한다. 즉, 가장 긴 변을 c라고 하고 나머지 변들을 a, b라고 한다면 a + b > c를 만족해야만 삼각형을 만들 수 있는 것이다.

 

 입력으로 주어진 nums를 오름차순으로 정렬해주고 for문으로 배열의 인덱스 2부터 끝까지 진행한다. for문에서 선택되는 변은 c에 해당하고 나머지 두 변은 left와 right에 위치한다. 즉, nums[left] + nums[right] > nums[i]와 같은 조건을 만족하는 개수를 카운트 해주면 된다.

        for i in range(2, len(nums)):
            left = 0
            right = i - 1

            while left < right:
                if nums[left] + nums[right] > nums[i]:
                    answer += right - left
                    right -= 1
                else:
                    left += 1

 

 위의 코드에서 answer += right - left를 해줬는데 이는 rights는 고정된 상태로 left의 가능한 변의 개수를 카운트하는 것이다. 즉, left <= x < right에 해당하는 인덱스의 개수를 카운트하는 것이다. 그 후 right를 앞쪽으로 한 칸 이동시켜서 이를 반복한다.

 만약 삼각형의 조건에 만족하지 못한다면 left를 +1해줘서 left에 해당하는 변의 크기를 증가시킨다(물론 중복된 값이 있기 때문에 같을수도 있지만). 이를 반복하면 만들 수 있는 삼각형의 개수를 구할 수 있다.

 

코드

[Swift]

class Solution {
    func triangleNumber(_ nums: [Int]) -> Int {
        var answer: Int = 0
        
        if nums.count < 3 {
            return 0
        }
        
        let numsSort: [Int] = nums.sorted()
        
        // i는 가장 긴 변의 길이에 해당하는 인덱스
        // left와 rights는 나머지 두 변에 해당하는 인덱스이다.
        for i in 2..<numsSort.count {
            var left: Int = 0
            var right: Int = i - 1
            
            // 만약 삼각형의 조건에 해당된다면 right-left만큼을 answer에 더해준다.
            // right는 고정된 길이이고 left에 해당하는 변의 개수를 카운트 해주는 것이다.
            // ex. [2, 3, 3, 4]에서 left : [0], right : [2], i : [3]이라면
            // 2, 3, 4 & 3, 3, 4 -> 2개(right-left)가 가능하다.
            while left < right {
                if numsSort[left] + numsSort[right] > numsSort[i] {
                    answer += right - left
                    right -= 1
                } else {
                    left += 1
                }
            }
        }
        
        return answer
    }
}

 

[Python]

class Solution(object):
    def triangleNumber(self, nums):
        answer = 0

        nums.sort()

        # i는 가장 긴 변의 길이에 해당하는 인덱스
        # left와 rights는 나머지 두 변에 해당하는 인덱스이다.
        for i in range(2, len(nums)):
            left = 0
            right = i - 1

            while left < right:
                # 만약 삼각형의 조건에 해당된다면 right-left만큼을 answer에 더해준다.
                # right는 고정된 길이이고 left에 해당하는 변의 개수를 카운트 해주는 것이다.
                # ex. [2, 3, 3, 4]에서 left : [0], right : [2], i : [3]이라면
                # 2, 3, 4 & 3, 3, 4 -> 2개(right-left)가 가능하다. 
                if nums[left] + nums[right] > nums[i]:
                    answer += right - left
                    right -= 1
                else:
                    left += 1

        return answer