99클럽 코테 스터디 2일차 TIL + 유클리드호제법/GCD

💡문제

[level 2] 숫자 카드 나누기 - 135807

문제 링크

성능 요약

메모리: 124 MB, 시간: 34.15 ms

---

 

🤔접근법

문제 요약

• 배열 A의 정수들을 모두 나눌 수 있는 숫자 a는 배열 B의 정수를 하나도 나눌 수 없다.
• 배열 B의 정수들을 모두 나눌 수 있는 숫자 b는 배열 A의 정수를 하나도 나눌 수 없다.
• 숫자 a와 b중 큰거를 출력

범위 체크 및 시간복잡도 예상

• 1 ≤ 배열의 길이 ≤ 500,000
• 1 ≤ 배열의 원소 ≤ 1,000,000
• O($N$) 이하.

풀이법

⭕ 접근 방법. 유클리드 호제법

1. 배열 A의 최대 공약수를 구한다.
2. 배열 B의 최대 공약수를 구한다.
3. 배열 A의 최대 공약수가 배열 B의 원소 중 하나라도 나눌 수 있는지 확인한다.
4. 배열 B의 최대 공약수가 배열 C의 원소 중 하나라도 나눌 수 있는지 확인한다.

➡️ 해당 풀이법의 시간 복잡도 : $O(NlogN)$ 을 넘는거 같은데.. 이게 왜.. 돌아가냐

---

🤯FAIL

답을 봐서 문제를 푼 경우

• 유클리드 호제법을 사용해야한다는 것은 생각하고 있었는데
• 내가 생각하는 풀이가 시간복잡도가 계속 넘어가는거 같아서 풀이의 갈피를 못잡고 결국 답을 봤다
• 유클리드 호제법.. 을 확실히 이해하지 못해서 이전에 써두었던 코드를 가져왔다
• 정수론 너무 어렵다
• 다시 공부하는걸로

---

👩‍💻 코드

import java.io.*;
import java.util.*;

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        
            int answer = 0;
            // arrayA의 최대 공약수 구하기 -> gcdA
            int gcdA = 0;
            for (int i = 0; i < arrayA.length; i++) {
                gcdA = GCD(gcdA, arrayA[i]);
            }

            // arrayB의 최대 공약수 구하기 -> gcdB
            int gcdB = 0;
            for (int i = 0; i < arrayB.length; i++) {
                gcdB = GCD(gcdB, arrayB[i]);
            }

            // gcdA로 arrayB의 원소들 중 나눠지는 원소가 있는지 확인
            for (int i = 0; i < arrayB.length; i++) {
                if(arrayB[i] % gcdA == 0){
                    gcdA = 0;
                    break;
                }
            }

            // gcdB로 arrayA의 원소들 중 나눠지는 원소가 있는지 확인
            for (int i = 0; i < arrayA.length; i++) {
                if(arrayA[i] % gcdB == 0){
                    gcdB = 0;
                    break;
                }
            }

            // gcdA와 gcdB 중에 큰 수
            answer = Math.max(gcdA, gcdB);

            return answer;
        }

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