거의 이등변 삼각형이란?
거의 이등변 정수 삼각형(Almost Isosceles Integer Triangle)은 세 변의 길이가 모두 정수이면서, 두 변의 길이 차이가 정확히 1인 특수한 삼각형입니다. 이름 그대로 이등변 삼각형에 매우 가깝지만 완전히 같지는 않은 형태를 띱니다.
문제 정의
목표 둘레를 나타내는 숫자 하나를 인수로 받는 JavaScript 함수를 작성해야 합니다.
이 함수는 입력된 둘레 값보다 크지 않으면서 그 값에 가장 근접한 둘레를 가진 거의 이등변 삼각형의 세 변 길이를 찾아 반환해야 합니다.
예를 들어 원하는 둘레가 500이라면, 조건을 만족하는 삼각형은 다음과 같습니다.
[105, 104, 181]
실제 둘레는 105 + 104 + 181 = 390으로, 500 이하에서 조건을 만족하는 가장 큰 둘레입니다.
풀이 코드
다음은 해당 문제를 해결하는 코드입니다.
const perimeter = 500;
const almostIsosceles = (perimeter = 0) => {
let a = perimeter;
for(; a > 0; a--){
for(let b = perimeter; b > 0; b--){
for(let c = perimeter; c > 0; c--){
if(a + b + c > perimeter || a !== b + 1 || (Math.pow(a, 3) - Math.pow(b, 3) !== Math.pow(c, 2))){
continue;
};
return [a, b, c];
};
};
};
return [];
};
console.log(almostIsosceles(perimeter));
출력 결과
[ 105, 104, 181 ]
코드 동작 방식
이 코드는 세 개의 중첩 반복문으로 가능한 모든 변의 조합을 탐색하는 브루트 포스(완전 탐색) 방식입니다. 각 조합마다 다음 세 가지 조건을 검사하고, 하나라도 만족하지 않으면 건너뜁니다.
- 둘레 조건: 세 변의 합(a + b + c)이 목표 둘레를 초과하면 제외합니다.
- 거의 이등변 조건: a와 b의 차이가 정확히 1이어야 합니다(a === b + 1).
- 수학적 성질: a³ − b³ = c² 를 만족해야 합니다. 이 조건은 거의 이등변 정수 삼각형을 판별하는 핵심 기준입니다.
모든 조건을 통과하는 첫 번째 조합을 발견하면 즉시 [a, b, c] 배열로 반환하고, 끝까지 찾지 못하면 빈 배열을 반환합니다.
성능 개선 아이디어
위 코드는 시간 복잡도가 대략 O(n³)이라 입력값이 커지면 매우 느려집니다. 그러나 b는 항상 a − 1로 고정되고, c는 a³ − b³의 제곱근으로 바로 계산할 수 있으므로 반복문 하나만으로도 해를 구할 수 있습니다.
const almostIsoscelesFast = (perimeter = 0) => {
for(let a = Math.floor(perimeter / 3); a > 1; a--){
const b = a - 1;
const diff = a ** 3 - b ** 3;
const c = Math.sqrt(diff);
if(Number.isInteger(c) && a + b + c <= perimeter){
return [a, b, c];
}
}
return [];
};
console.log(almostIsoscelesFast(500)); // [ 105, 104, 181 ]a는 삼각형의 최장 변 후보이므로 둘레의 1/3부터 내림차순으로 탐색하고, 세제곱의 차가 완전제곱수인 경우에만 결과를 반환합니다. 이렇게 하면 시간 복잡도를 O(n) 수준으로 크게 줄일 수 있습니다.