문제 소개
숫자 배열 arr을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.
함수의 목표는 배열에서 세 개의 숫자(트리플렛)를 골랐을 때, 이를 삼각형의 세 변의 길이로 사용할 수 있는 경우의 수를 모두 세는 것입니다.
삼각형이 성립하려면 가장 긴 변의 길이가 나머지 두 변의 길이의 합보다 작아야 합니다. 즉, 세 변을 a ≤ b ≤ c라고 할 때 a + b > c를 만족해야 합니다.
예시
예를 들어 함수에 다음과 같은 입력이 주어진다면,
const arr = [2, 2, 3, 4];
출력은 다음과 같아야 합니다.
const output = 3;
출력 설명
삼각형을 만들 수 있는 유효한 조합은 다음과 같습니다.
2, 3, 4 (첫 번째 2 사용) 2, 3, 4 (두 번째 2 사용) 2, 2, 3
따라서 정답은 3입니다.
접근 방법
효율적인 풀이를 위해 다음 전략을 사용합니다.
1단계: 배열을 오름차순으로 정렬합니다. 정렬하면 각 쌍 (i, j)에 대해 세 번째 숫자가 될 수 있는 범위를 연속된 구간으로 찾을 수 있습니다.
2단계: 두 개의 포인터 i와 j를 사용해 첫 번째 변과 두 번째 변을 고정합니다. 그런 다음 k 포인터를 이동시키면서 arr[i] + arr[j]보다 작은 값들의 개수를 셉니다.
3단계: 인덱스 j+1부터 k-1까지의 요소는 모두 arr[i] + arr[j]보다 작으므로, 각 (i, j) 쌍마다 k - j - 1개의 유효한 삼각형이 만들어집니다.
이 방식은 무작정 세 가지 조합을 모두 확인하는 O(n³) 브루트 포스보다 훨씬 빠른 O(n²) 시간 복잡도로 문제를 해결할 수 있습니다.
코드 구현
전체 코드는 다음과 같습니다.
const arr = [2, 2, 3, 4];
const countTriangle = (arr = []) => {
arr.sort((a, b) => a - b)
let count = 0
for (let i = 0; i < arr.length - 2; i++) {
let k = i + 2
for (let j = i + 1; j < arr.length - 1; j++) {
k = Math.max(k, j + 1)
while (k < arr.length && arr[k] < arr[i] + arr[j]) {
k += 1
}
count += k - j - 1
}
}
return count
};
console.log(countTriangle(arr));코드 설명
arr.sort((a, b) => a - b): 배열을 오름차순으로 정렬하여 큰 값을 기준으로 탐색 범위를 좁힙니다.- 바깥쪽 루프의
i는 첫 번째 변, 안쪽 루프의j는 두 번째 변을 담당합니다. k는 세 번째 변이 될 수 있는 경계를 가리키며,arr[k] < arr[i] + arr[j]가 참인 동안 계속 이동합니다.count += k - j - 1: 현재 (i, j) 쌍으로 만들 수 있는 삼각형의 개수를 누적합니다.
실행 결과
콘솔 출력 결과는 다음과 같습니다.
3
배열 [2, 2, 3, 4]에서 만들 수 있는 삼각형은 총 3개로, 예상했던 결과와 일치합니다.