Codility Lesson10 - MinPerimeterRectangle

🔍 문제

---

어떤 직사각형의 넓이 N이 주어지면, 가능한 둘레 중 가장 작은 둘레를 반환 하는 문제이다.

 

MinPerimeterRectangle coding task - Learn to Code - Codility

 

✏️ 풀이 - JS

---

직사각형의 넓이 N은 두 변의 곱이다. 따라서 가능한 두 변의 길이는 넓이 N의 약수라고 할 수 있다. 둘레의 공식은 (A + B)*2 이므로 A+B의 값이 제일 작은 약수의 조합을 찾으면 된다.
이전에 풀었던 CounterFactors 문제와 비슷한 방식으로 풀어보았는데, N의 제곱근을 기준으로 N의 제곱근 보다 작은 약수들 중 가장 큰 약수의 짝이 더했을 때 가장 작은 값이 된다. 따라서 N의 제곱근 보다 작은 약수들 중 가장 큰 약수 구한 후, 그 값의 짝인 약수를 구해서 둘레를 반환해주었다.
하지만 만약 N의 제곱근이 정수라면, N의 제곱근을 변으로 하는 정사각형의 둘레가 가장 작기 때문에 이 경우에는 N의 제곱근*4을 반환해주었다.

시간복잡도 O(sqrt(N))로 정확도, performance 모두 100%가 나왔다.

function solution(N) {
    let side = 1;

    if(N === 1) return side*4; //사각형 넓이가 1인 경우

    if(Math.sqrt(N) % 1 === 0) return Math.sqrt(N) * 4; //N의 제곱근이 정수인 경우

    for(let i = 2; i < Math.sqrt(N); i++){
        if(N % i === 0) {
            side = i;    
        }
    }

    let theOther = N / side; 

    return (side + theOther)*2;
}