[LeetCode] 611. Valid Triangle Number

문제 출처: https://leetcode.com/problems/valid-triangle-number/

Valid Triangle Number - LeetCode

 

문제

정수 배열 nums에서 삼각형을 만들 수 있는 세 정수의 수를 반환할.

 

예제

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

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

 

풀이

문제를 보고, 처음 떠올린 생각은 다음과 같다.

• 배열에서 3개의 원소를 선택해야 하네? : 조합(Combination) 을 구하자.
• 뽑힌 3개의 정수로 삼각형을 만들 수 있을까?
  • 세 정수 중 최대 값이 나머지 두 정수의 합보다 작아야 함

var triangleNumber = function(nums) {
    let ans = 0;
    function combination(res, start, r) { 
        if (r == 0) {
            const maxVal = Math.max(...res);
            const sum = res.reduce((a, b) => a+b);
            if (sum - maxVal > maxVal) { ans += 1; }
        }
        for (let i = start; i < nums.length; i++) {
            res.push(nums[i]);
            combination(res, i+1, r-1);
            res.pop();
        }
    }
    combination([], 0, 3);
    return ans;
};

이러한 Brute Force 방식의 접근 방법의 경우, 시간초과(TLE) 를 발생시킨다.

 

현재 알고리즘에서 가장 문제가 되는 부분인 3개의 정수를 선택하는 과정을 조금 최적화 시켜볼 수 있다. 주어지는 배열을 오름차순으로 정렬하고, 세 개의 인덱스(i < j < k)를 이용하여 각 값을 순차적으로 접근하며 삼각형 판별을 수행할 수 있다. 다음 코드를 보자.

var triangleNumber = function(nums) {
    let ans = 0;

    nums = nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length-2; i++) {
        for (let j = i+1; j < nums.length-1; j++) {
            let k = j+1;
            while(k < nums.length && nums[i]+nums[j] > nums[k]) { ans += 1; k+= 1; }
        }
    }

    return ans;
}

이중 반복문 안에 있는 while 구문을 통해서 삼각형을 만들 수 없는 상태가 되면, k를 증가시키며 삼각형을 체크하는 과정을 멈추고 바로 다음 j로 이동하게 되어, 조합을 이용했던 이전보다 확인해야되는 케이스가 줄었음을 알 수 있다.

 

실제로 이 코드를 제출해보면, Accepted를 받을 수 있다. 그럼에도 실행시간이 868 ~ 1496ms로 효율적인 방식이라 하기는 아쉬움이 있다.

 

현재의 접근방법에서 더 최적화를 한다고 하면, 이중 반복문 안에서 while문을 통해서 k의 임계 위치를 찾는 것을 이진 탐색을 이용해서 찾는 방식으로 바꿀 수 있다.

var triangleNumber = function(nums) {
    let ans = 0;

    nums = nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length-2; i++) {
        for (let j = i+1; j < nums.length-1; j++) {

            // Binary Search!!!
            let low = j+1, high = nums.length;
            while (low < high) {
                const mid = low + Math.floor((high-low)/2);

                if (nums[i]+nums[j] > nums[mid]) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            ans += (low - 1 - j);

        }
    }

    return ans;
}

이진탐색을 이용할 경우, 실행 시간은 평균적으로 440ms로 이전보다 약 2배 정도 빨라진 것을 확인할 수 있다.

 

지금까지는 이중 반복문으로 2가지 정수를 선택 후, 마지막 정수를 변경하면서 삼각형 여부를 체크하는 방식을 사용하였다. 이제는 관점을 달리하여 정수 하나를 선택하고 이를 기준으로 나머지 두 정수를 찾는 방식으로 문제를 풀 수 있다.

 

이전과 마찬가지로 주어진 정수를 오름차순으로 정렬한 후, 삼각형 탐색을 수행한다. 위에서 언급한 것처럼 한 정수를 선택하는데, 이 정수를 우리가 찾을 세 정수 중 가장 큰 정수로 생각할 것이다. 그렇다면, 나머지 두 정수는 선택한 정수의 왼쪽에 위치해야 한다.

 

nums[i]를 가장 큰 변으로 갖는 삼각형의 개수를 찾는다고 가정해보자. 나머지 두 변을 각각 low와 high가 가리키는 곳의 값이라고 하고 low = 0, high = i-1로 초기화한다. 세 지점을 모두 선정했으니, 삼각형 가능 여부를 체크한다. 결과에 따라 두 가지 케이스를 생각할 수 있다.

• nums[low] + nums[high] > nums[i] : 삼각형 가능
  • 현재 high가 고정이라 할 때, low값이 high-1이 되는 케이스까지 삼각형이 가능
  • high = high - 1
• nums[low] + nums[high] <= nums[i] : 삼각형 불가능
  • low = low + 1

var triangleNumber = function(nums) {
    let ans = 0;

    nums = nums.sort((a, b) => a - b);

    for (let i = 0; i < nums.length; i++) {
        let low = 0, high = i-1;
        while (low < high) {
            if (nums[low] + nums[high] > nums[i]) {
                ans += high - low;
                high -= 1;
            } else {
                low += 1;
            }
        }
    }

    return ans;
}

 

Github: 611.js

opwe37/Algorithm-Study