[LeetCode] 611. Valid Triangle Number | LIM

문제

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

Valid Triangle Number - LeetCode

 

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

 

Example1

Input: nums = [2,2,3,4]
Output: 3
Explanation: Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

 

 

Example2

Input: nums = [4,2,3,4]
Output: 4

 

설명

주어진 배열에서 삼각형을 만들 수 있는 3개의 길이를 구하면 된다. 중복된 숫자가 있을 수 있는데 그 중복된 숫자까지 고려해서 삼각형을 만들 수 있는 3개의 길이를 구하면 되는 것이다. 

 

 

푼 방식

1. 배열을 sorting 한다.

(삼각형이 만들어지는 조건은 가장 긴 대변의 길이가 나머지 두 변의 길이의 합보다 작아야하기 때문이다.)

2. 왼쪽, 오른쪽, 가장 긴 변을 탐색하면서 삼각형을 만족하는 지 찾는다. 

3-1. 삼각형이 된다면 count += 1 을 한다.

3-2. 삼각형이 되지 않는다면 오른쪽으로 이동한다.

3-3. 오른쪽을 모두 체크했으면 왼쪽에서 1을 증가시킨 후 오른쪽 포인터도 왼쪽 옆으로 이동시킨다.

4. 위 과정을 반복한다. 

 

코드

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        count = 0
        nums.sort()
        left, right = 0, 1
        while left < len(nums) - 2:
            while right < len(nums) - 1:
                side = right + 1
                shorts = nums[left] + nums[right]
                while side < len(nums):
                    if shorts > nums[side]:  # 삼각형이 만들어지는 조건
                        count += 1
                        side += 1
                    else:
                        break
                right += 1
            left += 1
            right = left + 1
        return count

 

하지만 이 방법은 시간 초과가 발생했다..🥲

 

Solution 참고

1. 동일하게 배열을 sorting 한다.

2. 가장 긴 변을 for loop 으로 체크한다.

3. 왼쪽을 왼쪽 끝, 오른쪽은 가장 긴 변의 길이 바로 앞의 길이로 세팅한다.

4. 삼각형을 만족하면 오른쪽 위치에서 왼쪽 위치 뺀 값을 더해준다. 

2, 3, 5, 6, 7 이 있다고 가정 후 왼쪽은 2 에 있고, 오른쪽은 6에 있고, 가장 긴변은 7이라고 가정
이렇게 되면 이미 sorting 을 시켜놓았기 때문에 (2, 6, 7), (3, 6, 7), (5, 6, 7) 모두 삼각형 만족

따라서 왼쪽 위치 0, 오른쪽 위치3 이었을 때 3-0 하면 3개가 나오게 된다.

5. 삼각형을 만족하지 않으면 왼쪽 숫자를 증가시킨다.

 

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

 

결과

 

이 문제는 3Sum 문제와도 유사하다. 어쨌든 이 문제도 3개의 숫자를 구해서 합을 비교해야 하는 문제이기 때문에 같이 참고하면 좋을 것 같다. 

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

3Sum - LeetCode