숫자 카드 나누기 [자바]

🧫 문제 분석

✔️ 출처

숫자 카드 나누기 level 2

📖 문제

 

영희, 철수 각각 하나의 카드를 선택해서 소인수 분해 후

분해한 수들을 영희 카드와 철수카드를 나눠본다. 

 

영희 카드 중 하나를 소인수분해 했을 경우

영희 자신의 모든 카드 수는 소인수로 나눠지면서, 철수 것은 나눠지면 안된다. 

 

반대의 경우도 마찬가지이다. 

 

---

🔅 문제 풀이

import java.util.*;

class Solution {
    
    // 가장 작은 수 선택후 소인수 분해
    // 분해된 수들로 해당 배열을 다 나눠본다. boolean으로 나눠지는지 확인
    // 다 나눠지면 상대 카드들을 나눠본다. boolean으로 나눠지는지 확인
    int max = 0;
    
    
    public int solution(int[] arrayA, int[] arrayB) {
        Set<Integer> setA = new HashSet<>();
        Set<Integer> setB = new HashSet<>();

        getPrimeFactorization(setA, arrayA[0]);
        getPrimeFactorization(setB, arrayB[0]);
        
        checkDiv(setA, arrayA, arrayB);
        checkDiv(setB, arrayB, arrayA);


        return max;
    }
    
    
    // 소인수 분해 
    private void getPrimeFactorization(Set<Integer> set, int n) {
        set.add(n);
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                set.add(i);
                set.add(n / i);
            }
        }
    }
    // 자신 것을 나눠서 나눠지는지 확인 
    private void checkDiv(Set<Integer> baseSet, int[] base, int[] target) {
        for (int n : baseSet) {
            boolean check = true;
            
            for (int j = 0; j < base.length; j++) {
                // 자신 것이 안나눠지거나 타겟이 나눠지면 멈춤
                if (base[j] % n != 0 || target[j] % n == 0) {
                    check = false;
                    break;
                }
            }
            
            // 두 조건을 만족하면 최댓값 찾기
            if (check) max = Math.max(n, max);
        }
    }
}

 

🔅 리팩토링

❗ 오답노트 / 필요한 지식

1. 처음에는 오름차순 정렬해서 가장 작은 수의 소인수를 얻어 나눌라했는데 굳이 그럴필요 없었다. 아무 거나 하나 잡아서 소인수 분해 하고, 소인수로 가진 카드가 다 나눠져야하기 때문에 굳이 정렬하지 않아도 된다.