[프로그래머스 Lv.2] 카펫 (JS)

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

풀이1)

첫번째 풀이는 노란 영역의 가로와 세로를 w, h로 두고 넓이의 약수를 이용하여 길이를 구함

function solution(brown, yellow) {
    let answer = [];
    // w >= h
    // w * h = yellow => w, h는 yellow의 약수
    // w + h = (brown - 4) / 2
    let w = [], h = []
    for (let i=1; i<=Math.sqrt(yellow); i++) {
        if (yellow % i === 0) {
            h.push(i)
            w.push(yellow / i)
        }
    }
    
    for (let i=0; i<w.length; i++) {
        if (w[i]+h[i] === (brown-4)/2) {
            answer.push(w[i]+2)
            answer.push(h[i]+2)
        }
    }
    return answer;
}

실행 결과 >  메모리: 33.5 MB, 시간: 0.28 ms

 

풀이2) 이차 방정식 근의 공식 이용

전체 면적의 가로와 세로의 길이를 brown, yellow에 대하여 연립 방정식을 세우고 근을 구하는 방법

function solution(brown, yellow) {
    let a = 1, b = (2 + 0.5 * brown), c = brown + yellow
    let w1 = (b + Math.sqrt(Math.pow(b, 2) - (4*a*c))) / 2
    let w2 = (b - Math.sqrt(Math.pow(b, 2) - (4*a*c))) / 2
    return [w1, w2];
}

실행 결과 > 메모리: 33.6 MB, 시간: 0.07 ms

① S => w * h = brown + yellow (w >= h)
② brown = 2w + 2(h - 2) => h = (brown - 2w + 4) / 2

②번식을 ①번식의 h에 대입하여 S를 w에 대한 식으로 나타내면
=> w((brown - 2w + 4) / 2) = brown + yellow
위의 식을 w에 대한 이차 방정식으로 표현하면
=> w^2 - (2 + 0.5 * brown)w + (brown + yellow) = 0
근의 공식을 이용하여 w값을 구하면 된다. (근의 공식 = ( -b ± √(b^2 - 4ac) ) / 2)
∴ a = 1, b = - (2 + 0.5 * brown), c = brown + yellow
인데 위의 식에서 b의 -는 그냥 +로 바꿔 계산함