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

문제출처

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

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

class Solution {
    public long solution(int w, int h) {
        long answer = 1;
        int gcf = getGcf(w, h);

        answer = (long)w * h - (w + h - gcf);
        return answer;
    }
    
    public int getGcf(int w, int h){
        int a = w > h ? w : h;
        int b = w > h ? h : w;
        
        int tmp = a % b;
        if(tmp == 0) {return b;}
        while(tmp != 0){
            a = b;
            b = tmp;
            tmp = a % b;
        }
        return b;
    }
}

처음에 여러가지 경우의 수를 써보고 나온 결과는 최대공약수를 사용하는건가? 긴가민가 싶었는데 그게 맞았던거 같다.

다음 관건은 대각선이 지나는 칸은 어떻게 구할것인가? 였는데 이 역시 여러가지 경우의 수를 나열해놓고 보다보면 규칙이 보였는데

w + h - 최대공약수 였다. 처음에는 이렇게 간단할리가 없는데?

하면서 계속 여러가지 경우의 수를 집어넣어봤는데 얼추 다 맞아떨어져서 진행했고 정답이었다.

 

최대공약수를 구하는 방법은 유클리드호제법 << 검색해서 알아봤다.

a > b인 a와 b의 최대공약수는

a % b = r일때 b와 r의 최대공약수와 같다.

이를 나머지가 0이될때까지 반복해준다.

b % r = r' -> r과 r'의 최대공약수 구하기 반복...

 

코드를 조금 더 깔끔하게 고쳐보자면

getGcf에서 a와 b를 구하는 과정...

Math.max() Math.min()이 죽어도 생각이 안난다. 막상 이렇게 외우고 외워도 문제 풀때만 되면 저렇게 되어버리니...

 

그리고 지금 블로그 적다가 깨달은건데 15줄의 if문은 없어도 될거 같다...