[프로그래머스 JavaScript] 카펫

🚩  프로그래머스 Level2 카펫 -> 완전탐색

 

📖 문제 설명

카펫의 중앙에는 노란색, 테투리는 갈색으로 칠해져 있는 카펫이 있다.

노란색의 격자 수와 갈색의 격자 수가 주어질때, 총 카펫의 가로, 세로의 길이를 구하면 된다.

 

💡 1. (Tip) 카펫의 최소 높이는 3이라는 점이다. (위의 그림을 보면 이해된다.)

    2. 공식 : 갈색과 노란색의 합을 임의의 높이로 나눌때 나오는 높이와 가로 값을 토대로

       (가로-2) * (높이-2) = 노란색 격자 수 라면, 현재 높이, 가로의 길이를 찾은 것이다.

       (-2를 해서 곱한 이유는 양끝의 테투리가 갈색이기 때문에 빼고 계산해준다)

 

👉 소스 코드  ⏰시간복잡도 O(n)

function solution(brown, yellow) {
    var answer = [];
    let sum = brown + yellow;
    
    //카펫의 최소높이는 3부터이다.(위아래 갈색, 가운데가 노란색이기 때문에)
    for(let height=3; height<=brown; height++){
        //임의의 높이로 나눌때 나머지가 없을경우만
        if(sum % height === 0){
            //가로길이
            let weight = sum / height;
            
            //테두리를 제외한 길이를 구해야하기 때문에 각각 -2해준뒤 곱셈
            //결과가 yellow와 같다면 해당 높이와 길이 리턴
            if( (height-2) * (weight-2) === yellow){
                return [weight, height];
            }
        }
    }
    return answer;
}

 

👨‍💻 코드 설명

위의 문제 설명에서 임의의 높이로 나눈 가로값과 높이로 노란색 격자수를 비교해준다 하였다.

왜냐하면 노란색 격자수가 24라면,  노란색 격자의 가로, 높이가 12*2, 8*3, 6*4 등등 형태가 존재 한다.

따라서 임의의 높이로 나누었을때 나머지가 0일때만의 경우에서 그 임의의 (가로-2) * (높이-2)가 노란색 격자 수와

일치하면 정답이 된다.

 

 

📃https://mungto.tistory.com/43