[JAVA] 프로그래머스 : 멀쩡한 사각형 (Summer/Winter Coding(2019))

https://programmers.co.kr/learn/courses/30/lessons/62048?language=java

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

최대 공약수를 이용해서 구할 수 있을 거라고까지 밖에 생각 하지 못해서 다른 사람의 코드를 참고하였다.

 

해결 방안

간단하게 말해서 전체에서 선이 그어지는 구간(흰색 부분)을 빼는 문제이다.

하지만 선이 그어지는 부분을 알아내는 방법이 어려웠다. 

세로와 가로를 보고 각각 3칸 2칸 간격으로 일정하게 잘려지는 것을 보고 최대공약수의 영향을 받는다고 생각하였다.

한 패턴당 선이 그어지는 부분은 (w/gcd + h/gcd -1), 반복되는 패턴 갯수는 gcd 만큼이다.

참고
https://velog.io/@ajufresh/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%A9%80%EC%A9%A1%ED%95%9C-%EC%82%AC%EA%B0%81%ED%98%95-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-Java

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

 

* gcd 함수가 있다는 것을 발견하였다.

import java.math.* 라이브러리를 추가해주고
BigInteger.valueOf(int n1).gcd(BigInteger.valueOf(int n2))를 이용하여 gcd(최대공약수)를 구할 수 있다.

나중에 BigInteger로 구해진 값을 BigInteger변수.intValue()로 int형으로 바꿔줄 수 있다.

 

코드

import java.math.*;

// 멀쩡한 사각형
class Solution {
    public long solution(int w, int h) {
        long answer = 1;
        
        BigInteger num1 = BigInteger.valueOf(w);
        BigInteger num2 = BigInteger.valueOf(h);
        
        // 최대 공약수 구하는 함수
        int gcd = num1.gcd(num2).intValue();
        
        answer = ((long) w * (long) h) - ((((long) w / gcd) + ((long) h / gcd) - 1) * gcd);
        
        return answer;
    }
}