[프로그래머스/Level2] 멀쩡한 사각형 (JAVA)

📖 문제

 

프로그래머스

 

 

 

💡  풀이 방식

• 최대공약수

직접 그림을 그려보고 규칙을 파악할 수 있었다. (수학적 머리가 없으니 이렇게라도 하는 수밖에,,,퓨)

 

1. w와 h의 최대공약수를 구한다.

2. w*h에서 (w + h - w와 h의 최대공약수)를 뺀 값을 출력한다.

 

 

 

 

💥 유의사항

자료형 주의!!

int형으로 하면 틀리고, w와 h도 long으로 변환해줘야 한다,,

(w와 h를 곱하면 1억*1억이라 int형 범위를 넘어간다.)

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public long solution(int w, int h) {        
        long ww = (long)w;
        long hh = (long)h;
        
        return ww * hh - (ww + hh - getGCD(ww, hh));
    }
    
    // 최대공약수 구하는 메서드 (유클리드 호제법)
    private static long getGCD(long w, long h) {
        if(h == 0) return w;
        return getGCD(h, w%h);
    }
}

 

 

➕ 다른 풀이 방식

- BigInteger의 gcd 함수 사용!!! 우와....

import java.math.BigInteger;

public class Solution {

    public long solution(int w, int h) {
        long totalCount = (long) w * (long) h;
        long diagonalCount = w + h - BigInteger.valueOf(w).gcd(BigInteger.valueOf(h)).longValue();

        return totalCount - diagonalCount;
    }
}

---

💦 어려웠던 점

- 직접 그림 그리면서 최소공배수 아이디어 생각하는데 30분, 푸는 데 5분,, 틀린 거 고치는 데 5분

- 처음에는 w와 h의 홀홀/홀짝(짝홀)/짝짝 경우의 수를 나눠서 구해봤었다. (하지만 틀렸지)

 

- 이래도 로직은 맞았는데 long형으로 작성했다만 했으면 맞지 않았을까,,

- 그래도 최대공약수 아이디어를 혼자 힘으로 떠올려서 기쁘다~!~!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

[Java 자바] 프로그래머스 > Lv.2 멀쩡한 사각형

 

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

 

 

✔ 대각선이 지나는 단위 정사각형을 구하는 공식

대각선이 지나는 단위정사각형