[프로그래머스] 멀쩡한 사각형

문제 정보

• 프로그래머스 문제 링크
• 난이도 : level 2

 

해결 방법

멀쩡하지 않은 사각형은 나눈 줄에 의해 쪼개져야(?) 하므로 각 칸에서 위쪽 선의 위치와 아래쪽 선의 위치로 찾을 수 있습니다. 기울기가 w / h 로 고정적이므로 아래 그림과 같이 한 줄에 멀쩡하지 않은 사각형이 몇개나 나오는지 계산했습니다.

소스 코드

// 프로그래머스
// 코딩테스트 연습 > Summer/Winter Coding(2019) > 멀쩡한 사각형

function main(){
    let answer = new Array();
    let output = new Array();

    // 입출력 예 입력
    answer.push(solution(8, 12));
    answer.push(solution(10000000, 10000000));
    answer.push(solution(100000000, 100000000));
    output.push(80);
    output.push("?");
    output.push("?");
    
    console.log(`execution result`);
    for(let idx = 0; idx < answer.length; idx++){
        console.log(`#${idx}. answer:${answer[idx]} / correct answer:${output[idx]}`);
    }
}

/*
// w / h 로 기울기를 먼저 나눈 수 곱 연산을 할 경우 소수점 처리가 달라진다.
// W, H : 1억 이하의 자연수 이므로 BigInt 를 고려해야 한다.
function solution(w, h) {
    let answer = 0;

    for(let idx = 0; idx < h; idx++){
        const inclin = w / h; // 기울기
        const upperX = Math.floor(idx * inclin);
        const lowerX = Math.ceil((idx + 1) * inclin);
        const curFineSquare = w - (lowerX - upperX);
        //console.log(`upperX:${upperX} / lowerX:${lowerX} / curFineSquare:${curFineSquare}`);

        answer += curFineSquare;
    }

    return answer;
}
*/

function solution(w, h) {
    let answer = BigInt(0);

    for(let idx = 0; idx < h; idx++){
        const upperX = Math.floor(idx * w / h);
        const lowerX = Math.ceil((idx + 1) * w / h);
        const curFineSquare = w - (lowerX - upperX);
        //console.log(`upperX:${upperX} / lowerX:${lowerX} / curFineSquare:${curFineSquare}`);

        answer += BigInt(curFineSquare);
    }

    return answer;
}

main();

풀다가 2가지의 문제가 있었는데 첫 번째로 풀 때는 기울기를 구하느라 나눗셈을 먼저 수행했습니다. 그로인해 부동 소수점 오차가 발생하여 결과가 다르게 나왔습니다.

두 번째로 w, h 두 수가 1억까지 이므로 둘을 곱했을 경우 Number 타입은 -(2^53 - 1) 부터 2^53 - 1까지만 표현이 가능하기 때문에 BigInt 형으로 처리가 필요합니다. 

 

참고 자료

• MDN - BigInt
• MDN - JavaScript의 타입과 자료구조