프로그래머스 lv2. 카펫

1. 갈색 사각형과 노란색 사각형의 개수를 입력받는다.

2. 갈색 사각형은 테두리, 노란색 사각형은 내부를 차지한다.

3. 가로는 세로보다 길거나 같아야 한다.

 

최종적으로 만들어진 도형의 가로 길이, 세로 길이를 배열에 담아 리턴하라.

 

입력: (10, 2) 출력: [4, 3]

입력: (8, 1) 출력: [3, 3]

 

 

틀린 풀이

function solution(brown, yellow) {
    
    const sum = brown + yellow;
    const arr = [];
    const answer = [];
    
    for(let i = 1; i <= sum; i++){
        if(sum % i === 0) {
            arr.push(i)
        }
    }
    if(arr.length % 2 !== 0){
        answer.push(Math.sqrt(sum));
        answer.push(Math.sqrt(sum));
    } else {
        answer.push(arr[arr.length / 2]);
        answer.push(arr[arr.length / 2 - 1]);
    }
    return answer;
}

 

'갈색 사각형과 노란색 사각형의 합'의 약수를 모아다 놓고 약수의 중앙값 두개를 push해서 문제를 해결하려 했다.

만약 약수의 개수가 홀수면 무조건 제곱수이기 때문에 (ex. 9의 약수 1, 3, 9) 제곱근을 두번 push.

 

아직 반례가 뭔지는 모른다.

 

예를 들어 갈색 10개 노란색 2개면 총 12개고 약수는 1, 2, 3, 4, 6, 12 다.

애초에 노란색은 가운데 들어갈 수 밖에 없도록 개수가 주어져 있을테니 모양은 무조건 4X3 으로 나올 거라 생각했다.

근데 맞지 않나..??

 

만약 32를 입력받았다면 약수는 1, 2, 4, 8, 16, 32 => 내 이론 상 8X4 나와야 함

노란색만 봤을 때 6X2, 4X3 두가지 경우의 수가 나올 수 있다해도

그에 따른 갈색의 개수가 다르기 때문에, 모양은 항상 약수 중 가운데 걸로 정해질텐데..

(6X2 라면 갈색 개수 20 / 도형 크기 8X4 / 총 개수 32, 4X3 이라면 갈색 개수 18 / 도형 크기 6 X 5 / 총 개수 30)

 

반례를 꼭 찾아서 여기 기재하도록 해보겠다..

 

 

옳은 풀이

function solution(brown, yellow) {

    const arr = [];

    for(let height = 1; height <= Math.sqrt(yellow); height++){
        if(yellow % height === 0){
            const width = yellow / height;
            arr.push([width, height]);
        }
    }

    for(let i = 0; i < arr.length; i++) {
        if(arr[i][0] + arr[i][1] === (brown - 4) / 2) {
            return [arr[i][0] + 2, arr[i][1] + 2]
        }
    }
}

 

1. yellow의 약수를 height라고 정의한다.

2. width는 yellow / height 이고 배열에 [width, height] 를 push 한다.

3. [width, height] 쌍을 순회하면서 (brown 총 개수 - 4) / 2 와 같은 것을 찾는다.

4. 맞는 게 나타나면 그 때 [width + 2, height + 2] 를 리턴한다.