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

문제

프로그래머스 62048 멀쩡한 사각형 문제

가로(w), 세로(h)의 사각형에 1, 1격자가 그려져있다.

이 직사각형에 대각선을 그었을 때 대각선이 지나가지 않는 격자칸의 개수를 구하는 문제

시도했지만 실패

// 정사각형이면 w * w - w;
// 직사각형이면 w * h - (작은변 x 기울기올림)
function solution(w, h) {
    var answer = 1;
    if(w === h) answer = (w * w) - w;
    else {
        const gradient = h / w < 1 ? w / h : h / w;
        const smaller = w < h ? w : h;
        const num = Math.ceil(gradient);
        answer = w * h - (smaller * num);
    }
    return answer;
}

기울기로 문제를 푸려고 했는데 예외 상황들이 너무 많이 생김.

처음에는, 1 < 기울기 < 2, 2 < 기울기 < 3, ... 이런 식으로 기울기를 정수마다 나눠서 생각했었다.

그런데 1과 2 사이에 수 많은 기울기 값들 중에서 예외의 경우가 많았다.

1 < 기울기 < 1.5 의 상황을 예로 들자면, 작은변 x 2(2, 2, 2,...)가 아니라 2, 3, 2, 3, 2,...이렇게 반복된다.

그리고 answer값은 직각삼각형x2니까 무조건 짝수가 나와야 하는데(아닌가?) 홀수가 나올 때가 있어서

마지막에 if(answer % 2 !== 0) answer--; 이렇게 넣었었는데 짝수로 바꿔주긴 하지만 본질적인 문제는 이것이 아니었다.

이 외에도 많은 예외가 있었다. 그래서 결국 이 방법으로는 답을 찾기 어렵다는 결론!

 

찾아본 풀이 방법

카일의 코드를 분석했다.

 

w x h	전체칸 수	대각선 칸 수
3 x 1	3	3
3 x 2	6	4
3 x 3	9	3
3 x 4	12	6
3 x 5	15	7
3 x 6	18	6
3 x 7	21	9

 

x * 1  ⇒ 대각선 x칸

x * 2 ⇒ 대각선 x칸 + 1

x * 3 ⇒ 대각선 x칸 + 2 

...

이런 식으로 1씩 증가하는데, 두 수가 최대공약수가 1인 것만!

최대공약수가 1인 사각형의 대각선이 지나는 격자칸의 개수는 w + h - 1이 된다.

 

코드를 보면

function solution(w, h) {
  const multiple = gcd(w, h);
  const minW = w / multiple;
  const minH = h / multiple;
  const empty = minW+minH-1

  return w * h - multiple * empty;
}
// 최대공약수 구현 함수
function gcd(w, h) {
  let result = 1;
  let i = 2;
  while (w >= i && h >= i) {
    if (w % i === 0 && h % i === 0) {
      w /= i;
      h /= i;
      result *= i;
    } else {
      i++;
    }
  }
  return result;
}

empty는 w, h를 multiple로 나눴고,

empty에서 두 수를 더하고 -1을 해줬다.

 

리턴할 때는 empty를 다시 multiple에 곱해준다.

더 간단하게 함수를 만들면 아래처럼 코드를 줄일 수 있다....카일 천재🤭

function solution(w, h) {
  const multiple = gcd(w, h);
  return w * h - (w+h-multiple);
}