CODEKATA 119 ~ 120

119번 숫자 카드 나누기

/*
문제 분석
1. 정보
    - 철수와 영희는 선생님으로부터 숫자가 적힌 카드들을 절반씩 나눠 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려고 함
        - 1. 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
        - 2. 영희가 가진 카드들에 적힌 모든 수자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

2. 목표
    - 철수가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayA와 영희가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayB가 주어졌을 때, 주어진 조건을 만족하는 가장 큰 양의 정수 a를 return
3. 제약 조건
    - 1 <= arrayA의 길이 = arrayB의 길이 <= 500000
    - 1 <= arrayA의 원소, arrayB의 원소 <= 100_000_000

풀이
1. 아이디어
    - arrayA의 공약수와 arrayB의 공약수를 구하여 둘다 없고 가장 큰 정수를 return 하면 될 것이라 생각 함.
    - 추가적인 생각. 최대 공약수를 구한다면, 해당 공약수의 약수들이 결국 array의 공약수가 될 것이라 생각함.
    - 따라서 먼저 arrayA의 최대 공약수를 구하려고 함
        - 유클리드 호제법 사용하여 원소의 최대 공약수를 구함
        - 먼저 0번과 1번의 최대 공약수를 구하고, 이후 2번과 최대 공약수를 구하는 방식으로 마지막 원소까지 계산하여 최대 공약수를 구함
    - 최대 공약수를 구하였다면(gcdA, gcdB) 
        - gcdA가 arrayB의 모든 원소와 나누어 떨어지지 않는다면 성공
        - gcdB가 arrayA의 모든 원소와 나누어 떨어지지 않는다면 성공
        - gcdA와 gcdB 둘다 성공하였다면 둘중 더 큰 값 반환
*/

class Solution {
        public int solution(int[] arrayA, int[] arrayB) {

            int gcdA = getGCD(arrayA);
            int gcdB = getGCD(arrayB);
            int answer = 0;

            if (isAvailable(gcdA, arrayB)) {
                answer = gcdA;
            }

            if (isAvailable(gcdB, arrayA)) {
                answer = Math.max(answer, gcdB);
            }

            return answer;
        }

        private boolean isAvailable(int gcd, int[] arr) {
            for (int cur : arr) {
                if (cur % gcd == 0) {
                    return false;
                }
            }
            return true;
        }

        private int getGCD(int[] arr) {
            int result = arr[0];

            for (int i = 1; i < arr.length; i++) {
                result = gcd(result, arr[i]);
                if (result == 1) {
                    return 1;
                }
            }
            return result;
        }

        private int gcd(int a, int b) {
            if (b == 0) return a;
            return gcd(b, a % b);
        }
    }

120번 멀쩡한 사각형

/*
문제 분석
1. 정보
    - 가로 W, 세로 H인 직사각형 종이가 존재
    - 종이를 격자선을 따라 1cm X 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 해당 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았음.
    - 따라서 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태
2. 목표
    - 나누어진 종이에서 사용할 수 있는 정사각형의 개수를 return
3. 제약 조건
    - 1 <= W, H <= 100_000_000

풀이
1. 아이디어
    - 대각선은 중간에 정사각형이 겹치지 않는 좌표를 지날 수 있음 -> W와 H의 최대공약수를 구한 값 = gcd
        - (W / gcd, H / gcd) = (nw,nh)의 크기를 가진 직사각형이 gcd개 만큼 존재
        - 그렇다면 (nw, nh)의 크기를 가진 직사각형에서 잘린 정사각형을 제외한 크기는?
            - (nw - 1) * (nh - 1)
        - 잘린 사각형의 크기는 ?
            - nw * nh - (nw - 1) * (nh - 1) = nw + nh - 1
            - 결국 W * H - (gcd * (nw + nh - 1)값을 return
*/

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

            int nw = w / gcd;
            int nh = h / gcd;
            
            return (long) w * h - (long) (nw + nh - 1) * gcd;
        }

        private int gcd(int a, int b) {
            if(b == 0) return a;
            return gcd(b, a % b);
        }
    }