프로그래머스) 멀쩡한 사각형 풀이 (Java)

62048 - 멀쩡한 사각형

1) 문제 설명 요약 (원문은 링크 참고):

프로그래머스

 요약: 사각형의 가로 세로 길이 w와 h가 주어진다. 이를 1x1 크기의 정사각형 구역(cell)으로 구분하고 대각선으로 잘랐을 때 멀쩡한 형태로 남는 cell의 개수를 구하는 문제다. 

 

 조건: 1 <= w, h <= 100,000,000

 

 

2) 풀이 과정:

// 처음 풀이
import java.lang.Math;

class Solution {
    public long solution(int w, int h) {
        long answer = (long) w * h;
        if (w == h) return answer - w;
        // rotate to fit the function's requirement
        int max = Math.max(w, h);
        int min = Math.min(w, h);
        
        long prev = 0;
        for (int i = 1; i <= min; i++) {
            long cur = (long) max * i;
            long endIndex = (cur + min - 1) / min;
            answer = answer - (endIndex - prev);
            prev = cur / min;
        }
        
        return answer;
    }
}

 문제를 보고 떠올린 풀이는 대각선의 기울기를 구한 뒤, 높이나 너비 중 더 짧은 쪽을 기준으로 루프를 돌면서 해당 위치의 index와 이전 위치 index의 차이만큼 개수의 총 합인 w * h에서 빼는 방식으로 작성했었는데, 루프에서 Math를 사용하기 때문에 1억번을 루프하면 시간이 너무 길어지는 문제(시간 초과가 발생하지는 않음)가 있어 약간의 수정을 거쳐 위와 같이 Math 없이 계산하는 방법으로 수정했다. 그런데 문제를 풀고나서 알아보니 이렇게 일일이 계산하지 않고 최대 공약수를 이용하여 푸는 방법이 있었다.

문제에서 주어진 이미지 (w=8, h=12)

 

 w가 8이고 h가 12인 예시로, 총 16개가 제거되는 모습을 볼 수 있다. 여기서 16은 w와 h를 합한 수에서 최대공약수를 빼면 나오는 숫자다. 이 패턴은 w와 h가 둘 다 소수인 형태에서 확인하면 좀 더 명확한데, 예를들어 2와 5가 주어진 경우 cell의 총합은 10이고, 2와 5를 더한 7에서 두 수의 최대 공약수인 1을 뺀 6개의 cell이 잘려나가서 결과적으로 4개의 cell이 남게된다. 3 x 3의 정사각형이 주어진 경우에도 마찬가지로 9 - (6 - 3)인 6 개의 cell이 남는다. 이를 코드로 표현하면 다음과 같다.

 

 

3) GCD를 이용한 풀이:

class Solution {
    public long solution(int w, int h) {
        long answer = (long) w * h;
        if (w == h) return answer - w;
        
        if (h > w) {
            int tmp = h;
            h = w;
            w = tmp;
        }
        
        return answer - (w + h - getGCD(w, h));
    }
    
    private int getGCD (int a, int b) {
        int leftover;
        while (b != 0) {
            leftover = a % b;
            a = b;
            b = leftover;
        }
        return a;
    }
}

 

 

4) 주의할 점:

 이런 문제에서 항상 하는 실수가 형 변환 실수로 숫자가 다르게 나와 실패하는 경우다. 매번 long의 사용을 최소화할 방법을 궁리하다가 실수하는데, 되도록이면 모두 long으로 설정해서 우선적으로 문제의 정답을 맞추는데 집중하도록 해야겠다.