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

나의 풀이

function solution(brown, yellow) {
    var answer = [];
    for(i = 1; i < brown; i++){
        for(j = i; j < brown; j++){
            if(i*j==brown+yellow && (i-2)*(j-2)==yellow){
                answer[0]=i;
                answer[1]=j;
                break;
            }
        }
    }
    answer.sort((a,b)=>b-a);
    return answer;
}

• 전체 격자의 개수가 brown + yellow가 맞는지 확인
• 바깥쪽 brown을 제외한 안쪽 부분이 yellow가 맞는지 확인
• 맞는지 확인 후 저장
• 정렬

테스트에서 시간이 오래걸림(모든 i, j를 검사하면서 불필요한 연산 많음)

더 좋은 풀이

function solution(brown, yellow) {
    for (let height = 1; height <= Math.sqrt(brown + yellow); height++) {
        if ((brown + yellow) % height === 0) {
            let width = (brown + yellow) / height;
            if ((width - 2) * (height - 2) === yellow) {
                return [width, height];
            }
        }
    }
}

• 약수는 짝을 이루어 존재하므로 height ≤ sqrt(total)까지만 확인하면 됨
• width = total / height 이므로 반복문을 2번 돌리지 않아도 됨
• total의 약수인지 확인해서 width, height를 찾은 뒤 계산한 노란색 영역이 yellow와 같은지 확인