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

1. 문제

멀쩡한 사각형
https://school.programmers.co.kr/learn/courses/30/lessons/62048

2. 원래 틀린 코드

function solution(w, h) {
    var answer = 1;
    const prevW = w
    const prevH = h
    
    if(w === 1 || h === 1) {
        return 0
    }
    
    while(w%2 === 0 && h%2 ===0){
        w = w/2
        h = h/2
    }
    answer = (prevW*prevH) - ((w+h-1) * (prevW / w))
    
    return answer;
}

모든 상황을 다 생각해보지 못하고, width, height 둘이 동시에 2로 나눠지지 않을 때까지 2로 나누고 그 때의 x,y를 가지고 계산을 했다.

정말 잘못된 생각.

규칙을 찾을 때는 최대공약수를 고민해봐야한다.

3. 최대공약수, 최소공배수 구하기

3-1. 최대공약수

function getGCD(n1, n2){
	let gcd = 1
    for(let i = 2; i <= Math.min(n1,n2) ; i++){
    	if(n1 % i === 0 && n2 % i === 0){
        	gcd = i
        }
    }
	return gcd
}

3-2. 최소공배수

function getLCM(n1,n2){
	let LCM = 1
    while(true){
    	if(LCM % n1 === 0 && LCM % n2 === 0){
        	break
        }
      	LCM ++
    }
  return LCM
}

3-3. 유클리드 호제법

최대공약수 : getGCD(n1,n2)나 getGCD(n2, n1%n2)가 같다는 정의
최소공배수 : n1 * n2 = gcd * lcm에서 착안하여, lcm = (n1*n2)/gcd

const getGCD = (n1,n2) => n1 % n2 === 0 ? n2 : getGCD(n2, n1%n2);
const getLCM = (n1*n2)/getGCD(n1,n2)

4. 재도전

function solution(w, h) {
    var answer = w*h;
    const g  = w  % h ===0? h : getGCD(h,w%h)
    const nw = w / g
    const nh = h / g
    
    if(nw === 1 || nh ===1){
        if(nw === 1){         
            return answer - (nh * g)  
        }
        if(nh === 1) {
            return answer - (nw * g)
        }
    }
    else{
        return answer - (nh+nw -1) * g 
    }
}
function getGCD(a,b){
    let gcd = 1
    
    for(let i = 2; i <= Math.min(a,b); i++){
        if(a%i === 0 && b % i === 0){
            gcd = i
        }
    }
    return gcd
}

5. 더 좋은 풀이

function solution(w,h){
    const slope = h / w;
    let result = 0;

    for(let i = 1; i <= w; i++){
        result += Math.ceil(slope * i);
    }

    return ((h * w) - result) * 2;
}

기울기를 구해주고
w값까지 for문을 돌려 1씩 올려주는데
i * slope를 했을 때, 소수점이 나오면 ceil해서 올림을 한다.

이 이유는 1.3일 경우 사각형 하나에 위의 사각형을 0.3차지하기 때문에 총 사각형 2개를 먹게 되기 때문이다.

마지막 줄에서 ((h*w) - result) * 2에서 2를 곱하는 이유는 위아래가 기울기를 중심으로 대칭되기 때문이다.