[프로그래머스/java] 멀쩡한 사각형 - 유클리드 호제법 사용

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

 

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

 

 

이 문제는 유클리드 호제법 공식을 써야한다.

 

유클리드 호제법 공식 1

int gcd(int a, int b)
{
    int c;
	while(b)
	{
		c = a % b;
		a = b;
		b = c;
	}
    return a;
}

 

유클리드 호제법 공식 2

 public static int gcd(int p, int q)
 {
	if (q == 0) return p;
	return gcd(q, p%q);
 }

 

여러번의 풀이 시도를 했지만 계속 오류가 났었다. 유클리드 호제법만 알면 간단하게 풀릴거라 생각했다.

class Solution {
    public long solution(int w, int h) {
		long big = 0, small = 0;
		big = w;
		small = h;

		while(small != 0) {
			long n = big % small;
			big = small;
			small = n;
		}

		return w*h - (w + h - big);
    }
}

 

위의 코드는 문제가 있었다.

 

어디서 문제였는지 못찾았었는데

 

문제가 되는 부분은 바로

return w*h - (w + h - big);

 

return 부분이었다.

 

w (int) * h (int)  - ( w + h - big (long) );

 

연산의 결과가 int형식으로 계산되어서 int의 범위가 초과되면 일정 범위를 넘어설 때 값이 제대로 넘어가지 않는듯하다.

 

그래서 long 형 변수에 값을 넣어줘서 제대로 값이 계산되게 끔 해주어야 한다.

 

class Solution {
    public long solution(int w, int h) {
    	long big = w, small = h, answer = w;
    	
    	while(small != 0) {
    		long n = big % small;
    		big = small;
    		small = n;
    	}
        
        answer *= h;
        answer -= w + h - big;
    	
    	return answer;
    }
}

 

이렇게 하면 결과가 제대로 나온다.