본문 바로가기
개발/알고리즘

[프로그래머스] 카펫 (완전탐색/javascript)

by 자몬다 2021. 8. 26.

가운데는 노란색, 가장자리 한줄은 갈색인 카펫이 있다.

노란색 타일과 갈색 타일의 수가 주어졌을 때 카펫의 가로세로 길이를 리턴하는 문제다.

 

우선, 갈색 타일은 무조건 한 줄만 테두리쳐져 있으므로

결과는 [노랑타일의 너비+2, 노랑타일의 높이+2]가 될 것이다.

 

1. 주어진 yellow로 가능한 경우의 수를 구한다.

2. yellow로 가능한 형태 중, 주어진 brown과 일치하는 것을 찾는다.

3. 적합한 yellow 형태의 가로세로에 2씩 더한 값을 리턴한다.

 

yellow = 12인 경우의 가능한 경우의 수를 보자.

yellow 영역은 세로x가로가

[[1, 12], [2, 6], [3, 4]] 세 가지가 가능하다.

([4, 3], [6, 2], [12, 1]은 세로가 더 길게 되므로 조건에 맞지 않다.)

 

가능한 세로 길이를 구하려면

yellow의 약수를 구하면 된다.

 

12의 약수 = [1, 2, 3, 4, 6, 12]

 

세로가 더 긴 경우는 필요없으므로,

yellow의 약수 n의 제곱(가로세로가 같은 경우) > yellow 면 더이상 구할 필요 없다.

 

따라서 가능한 가로 세로 길이를 구하는 함수는 아래와 같다.

function divisors(integer) {
    let nums = [[1, integer]];
    for(var i=2; i < integer; i++) {
        if(i**2 > integer) return nums;
        if(integer % i == 0) {
            nums.push([i, integer/i]);
        }
    }
    return nums;
}

divisors(12); // [[1, 12], [2, 6], [3, 4]]

 

yellow 타일의 가능한 형태를 모두 구했으므로,

주어진 brown과 일치하는 형태를 찾아야 한다.

 

brown 타일의 갯수 공식은 아래와 같다.

(yellow 너비 + 2)*2 + (yellow 높이 * 2)

 

반복을 돌면서 brown과 일치하는 값을 찾았다면,

[yellow 너비+2, yellow 높이+2]를 리턴하면 된다.

 

 

전체 코드

function solution(brown, yellow) {
    // y로 만들 수 있는 높이/너비 길이의 경우의 수
    const yellows = divisors(yellow);
    // yellow의 크기별로 brown의 갯수를 구한다.
    const browns = [];
    for(let i in yellows){
        const h = yellows[i][0] // height 
        const w = yellows[i][1] // width
        if((w+2)*2+(h*2) == brown){
            return [w+2, h+2]
        }
    }
}

function divisors(integer) {
    let nums = [[1, integer]];
    for(var i=2; i < integer; i++) {
        if(i**2 > integer) return nums;
        if(integer % i == 0) {
            nums.push([i, integer/i]);
        }
    }
    return nums;
}

 

풀어보러 가기 : https://programmers.co.kr/learn/courses/30/lessons/42842

728x90

댓글0