카펫 carpet

💡

Level2 210922 https://programmers.co.kr/learn/courses/30/lessons/42842

문제 설명

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

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

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

제한사항

갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.

노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.

카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

brown

yellow

return

[4, 3]

[3, 3]

[8, 6]

My solution

처음에 DFS 함수를 사용하려다가 for문으로 1부터 yellow의 제곱근까지 돌면서 약수들을 검사해주면 되는 로직이라 재귀 한번 내려가는 게 무의미할 것 같아 for문만으로 바꾸었다.

for문 내에서는 약수임을 검사하기 위해 몫과 나머지를 구했고 이후 약수가 맞다면 tmp에 저장하였다.

tmp에 저장한 yellow의 약수를 통해 (가로가 같거나 더 길기 때문에) 가로, 세로를 +2씩 해서 이렇게 만들어진 가로와 세로 길이는 전체 크기를 구할 수 있는 값이 되었다.

처음에는 3개의 테스트케이스를 보면서 아래와 같이 (가로 약수 + 세로 약수)*2의 값에 모서리 4개를 더해준 것이 brown이 되는 것이 조건이라고 생각했다.

if (

하지만 정확성 69.2/100

틀릴 만한 조건은 저것 뿐이라 생각했다.

우선 이상한 것은 조건에서는 나오지 않는 연산인 tmp[0]+2, tmp[1]+2를 해야 그게 답이라는 것이었다.

이것만 해도 쉽게 유추할 수 있다. 조건에서도 tmp[0]+2, tmp[1]+2인 전체 카펫의 가로, 세로 길이를 사용해야 한다는 것을. 그렇다면 전체 카펫의 가로, 세로 길이를 구하는 것은 안되니 전체 카펫의 사이즈를 yellow, brown을 곱해 구할 수 있다는 사실을 알아야 했다. (사실 위 조건도 유효한 것이었다.)

하지만 똑같이 정확성 69.2/100 가 나왔다.

그 다음은 답을 구하자마자 값을 리턴해주면서 반복문을 빠져나와야겠다는 생각이 들었다. 처음에는 성능 때문인가 싶어서 수정했는데 제출해보니 100점이 나온다.

로직을 천천히 살펴보니 for문을 돌면서 remainder가 0인 경우 약수의 조건에 해당되고 바로 tmp가 다른 값으로 변해버리기 때문에 정작 원하는 약수를 찾았어도 다음 약수의 쌍으로 덮어씌워진 것이었다. 3개의 테스트케이스로 하면서 거기에 매몰되었던 것 같다. 정답을 찾자마자 break나 return을 하는 방식으로 문제를 풀어왔으니 잊지 않아야겠다는 생각도 들었다.

소스 코드

function solution(brown, yellow) {
    let answer = [];
    let tmp = [];

    for (let i = 1; i <= Math.sqrt(yellow); i++) {
        let quotient = yellow / i;
        let remainder = yellow % i;
        if (remainder === 0) {
            tmp[0] = Math.max(quotient, i);
            tmp[1] = Math.min(quotient, i);

            if ((tmp[0] + 2) * (tmp[1] + 2) === brown + yellow) {
                //if (4 + (tmp[0] + tmp[1]) * 2 === brown) {
                [tmp[0], tmp[1]] = [tmp[0] + 2, tmp[1] + 2];
                break;
            }
        }
    }
    return (answer = tmp);
}

test("solution", () => {
    // expect(solution(10, 2)).toStrictEqual([4, 3]);
    // expect(solution(8, 1)).toStrictEqual([3, 3]);
    expect(solution(24, 24)).toStrictEqual([8, 6]);
});