문제

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.

Example 1:

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

Example 2:

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

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

Python 풀이

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

문제 설명

nums 리스트에서 0에서 1000까지의 숫자가 담겨있는데, 이 숫자 3개를 선택해서 삼각형을 만들 수 있는 경우의 수를 구하는 문제이다.

접근법 & 코드 설명

솔직히 마음같아서 3중 for문 돌려서 풀고 싶었는데 개발자답지 못한 풀이이므로 다른 풀이 방법을 떠올리다가 binary search를 떠올렸다. 그런데 풀이 결과 속도가 너무 낮아서 다른 사람들의 풀이를 참고하여 풀었다.

일단 접근법은 비슷한데, 어떻게 효율적으로 코드를 짜는지가 관건이었다. 먼저 리스트를 오름차순으로 정렬시킨다. (이분 탐색을 이용하면 오름차순으로 정렬되어 있어야 한다.) 현재 풀이한 코드는 이분 탐색으로 풀진 않았지만 어쨋거나 오름차순으로 정렬되어 있어야 삼각형이 만들어지는 경우의 수를 일일이 계산하지 않고 한번에 계산할 수 있다.

그 후 2중 for문을 이용해서 작은 숫자부터 2개를 고른다. i < j 이고 nums[i] < nums[j]이다. 그리고 j <= k 인 k가 있다. 초기에 k = i + 2이다. 이제 while문을 이용해서 nums[i] + nums[j] > nums[k] 를 만족하는 동안 k를 1씩 증가시켜 준다. 즉, nums[k] >= nums[i] + nums[j] 이면 반복문을 종료한다. count += k - j - 1 은 아래서 자세하게 설명하겠다. 짧게 설명하면, 삼각형이 만들어지면 k값이 계속 증가되고, 어느 순간 nums[k]가 더 커지게 되면 반복문이 종료되므로 k가 증가한 만큼(삼각형이 만들어지는 경우의 수만큼)만 더해주는 것이다.

예시로 nums = [1, 1, 3, 5, 6, 6, 8, 10] 이라고 하면,
(편의상 nums[i] -> ni, nums[j] -> nj, nums[k] -> nk라고 함)

1. i = 0, j = 1, k = 2
   • ni = 1, nj = 1, nk = 3 : ni + nj < nk 이므로 k가 증가하지 않고 바로 반복문을 탈출한다.
   • count += k - j - 1 : count += 2 - 1 - 1 = 0 : 0만큼 카운트를 올린다. 당연하게도 만들 수 있는 삼각형이 없어서 0이 된다.
2. i = 0, j = 2, k = 2
   • ni = 1, nj = 3, nk = 3 : ni + nj > nk 이므로 k 1증가 -> k = 3
   • ni = 1, nj = 3, nk = 5 : ni + nj < nk 이므로 반복문 종료
   • count += k - j - 1 = 3 - 2 - 1 = 0
   • 이번에는 삼각형을 만들 수 있는 경우가 있었는데 왜 count가 증가하지 않을까? j랑 k가 같은 인덱스이기 때문이다. (서로 다른 3개의 숫자를 골라야함)
   • 결국 k가 반복문을 끝내고 나왔을 때 j의 바로 뒤에 있다면 k가 증가한 것이 아니게 된다.
   • j == k 이면 어쨋거나 k가 증가하게 되어있다. 왜냐면 ni + nj > nk에서 nj == nk 이고 ni가 양수니까 항상 만족한다. 따라서 k가 증가하지만 사실 이건 삼각형이 만들어진 경우라고 볼 수 없다.

이런 식으로 계속 하다보면 정답이 나온다. 그리고 count += k - j - 1인 이유를 설명하자면 리스트가
1, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 라고 생각해보자.
1, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
1, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
1, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
...
1, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
k는 마지막까지 가고서 반복문이 종료된다. 마지막 조건까지 만족한 k는 1이 증가되고 나서 반복문이 끝나기 때문에 j = 5, k = 13이고 k - j - 1 = 7이 된다. 실제로 삼각형을 만들 수 있는 경우의 수도 7가지였다.