[프로그래머스] 숫자 카드 나누기 (Java)

문제

프로그래머스

 

알고리즘

해시셋

 

풀이

arrayA, arrayB 가 오름차순으로 정렬되어있다고 가정하고 문제를 풀었다.

 

1. arrayA의 제일 작은 원소(0번째 원소)의 약수를 구해 해시셋 cdA에 삽입한다.

2. arrayA의 원소들이 cdA로 나누어떨어지지 않는다면 제거한다.

3. arrayB의 원소들을 모두 나눌 수 없는 cdA의 원소 중 최댓값을 구한다.

 

arrayB에 대해서도 마찬가지 작업을 하여 최댓값을 구하고, 두 값 중 최댓값을 반환한다.

---

약수 빠르게 구하기

약수를 구할 때 1부터 i 값까지 탐색하며 찾는 것이 아니라 i 의 제곱근까지만 찾아

num / i 를 같이 삽입해주면 연산 횟수를 i 에서 i 의 제곱근으로 줄일 수 있다.

 

예를 들어 i 가 100이라면 i의 제곱근인 10까지 탐색하며 다음 과정으로 약수를 구한다.

100 % 1 == 0 -> 1 과 100/1 삽입

100 % 2 == 0 -> 2 와 100/2 삽입

100 % 5 == 0 -> 5 와 100/5 삽입

100 % 10 == 0 -> 10과 100/10 삽입

 

i가 최대 1억이므로 위 방법으로 연산 수를 1억에서 √1억으로  줄일 수 있다.

 

코드

import java.util.*;

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        
        Set<Integer> cdA = getCdSet(arrayA[0]);
        Set<Integer> cdB = getCdSet(arrayB[0]);
        
        remove(arrayA, cdA);
        remove(arrayB, cdB);
        
        return Math.max(getMax(arrayA, cdB), getMax(arrayB, cdA));
    }
    
    public Set<Integer> getCdSet(int num) {
        Set<Integer> cdSet = new HashSet<>();
        
        for(int i=1; i*i<=num; i++) {
            if(num % i == 0) {
                cdSet.add(i);
                cdSet.add(num / i);
            }
        }
        
        return cdSet;
    }
    
    public void remove(int[] array, Set<Integer> cdSet) {
        
        for(int i=0; i<array.length; i++) {
            ArrayList<Integer> removeList = new ArrayList<>();
            
            for(int cd: cdSet)
                if(array[i] % cd != 0)
                    removeList.add(cd);
            
            for(int r: removeList)
                cdSet.remove(r);
        }
    }
    
    public int getMax(int[] array, Set<Integer> cdSet) {
        int max = 0;
        
        label1: for(int cd: cdSet) {
            for(int num: array) {
                if(num % cd == 0) continue label1;
            }
            
            max = Math.max(max, cd);
        }
        
        return max;
    }
}