멀쩡한 사각형 / js 풀이

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

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

문제풀이

이번 문제는 프로그래머스의 "Summer/Winter Coding 2019" 코딩 테스트에서 출제되었던 문제입니다.

이 문제를 스스로 풀기 위해 이런저런 고민을 다 해보았지만, 결국 구글의 도움을 받을 수 밖에 없었습니다.

 

이 문제는 단위 사각형으로 이루어진 직사각형의 대각선을 지나는 사각형의 개수를 알아내는 것이 포인트 입니다.

 

물론 직접 좌표의 개념을 도입하거나 선의 기울기를 활용하여 푼 분들도 있지만, 저로서는 아무리 머리를 싸매도 못했겠다 싶었던 해답이었습니다.

이 문제에 직접 연관이 있는 개념이 기술된 블로그를 함께 첨부하겠습니다.

https://m.blog.naver.com/PostView.nhn?blogId=zzinuhelios&logNo=120024685950&proxyReferer=https:%2F%2Fwww.google.com%2F

 

제가 푼 것이 아님에도 포스팅을 하는 이유는 이 문제를 풀면서 유클리드 호제법(유클리드 알고리즘)이라는 것을 알게되었기 때문입니다.

두 수의 최대 공약수를 구하는 알고리즘인데요. 두 수가 서로를 나누어가며 최종적으로는 원하는 수를 찾아내는 과정인데, 최종적으로 나머지가 0이 될때까지 서로를 나누고 남는 나머지로 다시 서로를 나누어가는 것입니다.

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

 

텍스트로 설명하기에는 이해가 잘 되지 않을 것 같아 아래 예제를 보겠습니다.

위 알고리즘을 활용하여, 아래 공식에 대입하면 문제의 답은 쉽게 도출이 됩니다.

 

대각선이 지나는 단위 정사각형의 개수  : W+H - (W, H의 최대공약수)

 

ㅎㅎ...

코드

function solution(w, h) {
    const g = gcd(w,h); // 최대공약수

    return (w*h)-(w+h-g); // 공식적용
}

function gcd(a, b){    // 유클리드 호제법
    const tmp = a%b;
    if(tmp === 0){
        return b;
    }
    else return gcd(b, tmp);
}

리뷰

대각선을 지나는 사각형의 개수를 구하는 문제의 공식을 알고 있거나, 문제를 보고 풀이법을 곧바로 생각해 낸 사람들에게는 어렵지 않았을 것 같습니다.

하지만 저는 그렇지 못했고 풀이를 보고도 당황스러웠기 때문에, 이 문제의 풀이를 찾아보는 과정에서 새로운 것을 배울 수 있었던 것 같습니다.