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

문제

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

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

풀이

구하는 값은 사용할 수 있는 정사각형의 갯수이다.

크게 식으로 보면 다음과 같다.

 

전체 정사각형의 갯수 - 사용할 수 없는 정사각형의 갯수 = 사용할 수 있는 정사각형의 갯수

 

이것은 다음과 같다.

 

w*h - ? = 사용할 수 있는 정사각형의 갯수

따라서 사용할 수 없는 정사각형의 갯수만 구할 수 있으면 문제를 풀 수 있다.

 

문제에서 주어진 예시 w=8 h=12를 보면 다음의 규칙을 발견할 수 있다.

가로 2칸 세로 3칸씩 똑같은 패턴을 가지는 직사각형이 반복된다.

이 직사각형에서 사용할 수 없는 정사각형의 갯수는 총 4개이다. 어떻게 하면 4라는 값을 유도할 수 있을까?

바로 2(가로) + 3(세로) - 1 을 해주면된다. 그렇다면 가로와 세로는 어떻게 구할까? 우리에게 주어진 값은 w=8, h=12가 있다.

가로:2 세로:3은 이 값에서 4씩 나누어 주면 구할 수 있는 숫자인데 4는 생각해보면 두 숫자의 최대공약수이다.

 

따라서 한 패턴에서 사용할 수 없는 정사각형의 갯수는 다음과 같다. 그러나 

w/최대공약수 + h/최대공약수 - 1

그리고 이러한 패턴은 최대공약수만큼 반복된다. 그래서 마지막에 최대공약수를 곱하면 다음과 같다.

(w/최대공약수 + h/최대공약수 -1)*gcd

즉, 이 값은 사용할 수 없는 정사각형의 갯수를 나타낸다.

이제 정답을 구할 수 있다.

 

 

주의할 점

1.제한 사항을 보면 w,h로 주어질 수 있는 값은 1억 이하다.

따라서 w*h할 시에 오버플로우가 발생해서 잘못된 값이 들어갈 수 있으므로

다음과 같이 형 변환을 명시적으로 해줘야한다.

 

(long) w * h

 

2. 최대공약수를 구하는 알고리즘은 암기하고 있자. 

static int getGCD(int a, int b) {

        if (b > a) {
            int temp = a;
            a = b;
            b = temp;
        }

        while(b != 0) {
            int r = a%b;
            a = b;
            b = r;
        }

        return a;
    }

 

혹시 최대공약수를 기억하기 어렵다면 BigInteger을 gcd 메소드를 이용해서도 간단히 구할 수 있다.

 

int gcd = BigInteger.valueOf(8).gcd(BigInteger.valueOf(12)).intValue();

 

코드

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

        answer = (long)w*h - (w/gcd + h/gcd -1)*gcd;

        return answer;
    }

    static int getGCD(int a, int b) {

        if (b > a) {
            int temp = a;
            a = b;
            b = temp;
        }

        while(b != 0) {
            int r = a%b;
            a = b;
            b = r;
        }

        return a;
    }

    @Test
    void test() {
        Assertions.assertEquals(80, solution(8, 12));
    }
}