[2023-02-09]

Start

ChocolatesByNumbers 문제

 

N과 M의 최대 공약수를 구해야하는 문제였다.

유클리드 호제법을 이용해서 빠르게 최대 공약수를 구했다.

 

CommonPrimeDivisors 문제

각각 나눠지는 소수가 같은지 파악하는 문제이다. 

아니 근데..왜이렇게 풀었는지 이해가 안간다..

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A, int[] B) {
        int result = 0, size = A.length;

		// 소수를 구하기 위한 배열 초기화
        boolean[] prime = new boolean[6001];
        // 에라토스테네스의 체로 소수 구하기
        for(int i = 2; i <= 6000; i++) {
            if (prime[i]) {
                continue;
            }
            for(int j = i + i; j <= 6000; j+=i) {
                prime[j] = true;
            }
        }
        
        for(int i = 0; i < size; i++) {
            int a = 0, temp = 0;
            int n = A[i], m = B[i];
            int max = A[i];
            
            if (n < m) {
                n = B[i];
                m = A[i];
                max = B[i];
            }
            
            // 최대공약수 구하기
            while(true) {
                if (n % m == 0) {
                    temp = m;
                    break;
                }
                a = m;
                m = n % m;
                n = a;
            }
            // 구한 최대 공약수가 1이면 prime divisor가 아니라고 생각했다.
            if (temp != 1) {
            	// 구한 최대 공약수로 세트 중 더 큰 수에 나눈다.
                int t = max / temp;
                // 일단 result값을 1 높인 다음 조건을 통과하지 못하면 1 빼기로 했다.
                result++;
                for(int j = 2; j <= 6000; j++) {
                	나눈 수가 소수로 나눠떨어지는데 세트 중 더 작은 수에도 나눠떨어질 경우.. (를 하고 싶었는데.. 영 다른 거 한듯..)
                    if (t % j == 0) {
                        if (!prime[j] && temp % j != 0 || !prime[t / j] && temp % (t/j) != 0) {
                            result--;
                            break;
                        }
                    }
                }
            }
        }

        return result;
    }
}

 

머리아파라ㅜㅜㅜ