코딩테스트(프로그래머스)_멀쩡한 사각형_2단계

코딩테스트(프로그래머스)_멀쩡한 사각형_2단계

728x90

https://programmers.co.kr/learn/courses/30/lessons/62048

[코딩테스트 연습 - 멀쩡한 사각형

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을

programmers.co.kr](https://programmers.co.kr/learn/courses/30/lessons/62048)

풀이

몇 개의 사례를 직접 그려보다 보면 GCD(The Greatest Common Divisor, 최대공약수)를 이용해서 풀면 되겠다는 생각이 들었다. 하지만 나는 그냥 직관적으로 방정식의 기울기를 이용해서 풀어봤고, 다행히 시간제한에 문제는 없어서 통과했다. 단, Javascript에서는 소수점 이하 계산이 부정확할 수가 있어서 y=h/w\*x 의 식을 곱하기를 먼저 해서 y=h\*x/w 로 바꾸어주었다.

numOfDel += Math.ceil(y) 를 하게 되면, 기울기의 선이 지나가는 아래쪽의 모든 사각형을 포함하게 되는데 이것을 전체 사각형에서 빼게 되면 기울기 선 기준으로 위쪽에 멀쩡한 사각형만 선택하는 것과 같다. 이를 x2 해주면 아래쪽 멀쩡한사각형도 구할 수 있게 됨.

아래 코드에서 주석처리된 부분은 처음에 기울기가 지나가는 부분의 삭제되는 부분만 구하는 걸로 해서 계산을 했는데, 다른 분의 풀이를 보다가 나와 같은 접근이지만 좀 더 간단하게 풀어서 나도 참고를 했다.

코드

function solution(w, h) { let numOfDel = 0 for(let x=1;x<=w;x++){ const y = h * x / w numOfDel += Math.ceil(y) } //console.log("numOfDel",numOfDel) return (w*h - numOfDel)* 2; } // function solution(w, h) { // let x = 1 // let numOfDel = 0 // let memoryY = 0 // while(1){ // const y = h * x / w // numOfDel += (Math.ceil(y) - memoryY) // if(Number.isInteger(y)) // break // memoryY = Math.floor(y) // x++ // } // // console.log("total:",total,"numOfDel",numOfDel,x,w/x, "=>",numOfDel*w/x) // return w*h - numOfDel*w/x; // }

from http://sbiografia.tistory.com/89 by ccl(A) rewrite - 2021-12-14 13:01:55