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

프로그래머스 알고리즘 고득점 kit - 완전 탐색(=brute force) 문제

문제

처음 접근 시도

function solution(brown, yellow) {
    var answer = [];
    let isTrue = false;
    let carpet = brown + yellow;
    for (let i = 1; i < 10; i++){
        for (let j = 1; j < 10; j++){
            if (i * j == carpet && i >= j){
                answer.push(i);
                answer.push(j);
                isTrue = true;
            }
        }
        if (isTrue) break;
    }
    return answer;
}

이 코드에서의 문제점

1. 범위 제한 문제

• 코드에서는 i와 j를 1부터 9까지의 범위로만 반복
• 실제 카펫의 셀 수(brown + yellow)는 매우 클 수 있으며, 이 경우 9×9 범위 내에서는 올바른 가로와 세로 값을 찾을 수 X

2. 조건 체크 문제

• 코드에서는 전체 격자 수(i * j == carpet)만 확인하고 있음
• 문제에서는 "테두리 1줄이 갈색"이고 내부가 노란 셀임을 보장해야 하므로, [width - 2] × [height - 2] 즉, 내부의 yellow 영역이 정확히 yellow와 일치하는지 체크하는 추가 조건이 필요

풀이 

function solution(brown, yellow) {
    const total = brown + yellow;

    // height는 최소 3부터 시작 (테두리 1줄 때문에 내부 최소 영역은 1x1 이상)
    for (let height = 3; height <= total; height++) {
        if (total % height === 0) {  // height가 total의 약수인 경우
            const width = total / height;
            // 문제 조건: width >= height
            if (width < height) continue;

            // 내부 영역의 셀 수 (width-2) * (height-2)가 yellow와 일치하는지 확인
            if ((width - 2) * (height - 2) === yellow) {
                return [width, height];
            }
        }
    }

    return [];  // 문제 조건상 항상 답이 있으므로 이 부분은 실행되지 않음
}

 

 

 

 

아직까지는 이렇게 조건을 완벽히 설계하는게 어렵지만 하다보면 언젠간 할 수 있겠지 😂