99클럽 코테 스터디 2일차 TIL / [프로그래머스] 숫자 카드 나누기

전종원·2024년 7월 23일

99클럽 TIL 개발자취업 코딩테스트준비 항해99

오늘의 학습 키워드

최대 공약수, 유클리드 호제법

문제

https://school.programmers.co.kr/learn/courses/30/lessons/135807

플랫폼: 프로그래머스
문제명: 숫자 카드 나누기
난이도: Lv2

풀이

개선 전

import java.util.*;

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        
        Arrays.sort(arrayA);
        Arrays.sort(arrayB);
        
        answer = Math.max(answer, calcBigestA(arrayA, arrayB));
        answer = Math.max(answer, calcBigestA(arrayB, arrayA));
        
        return answer;
    }
    
    public int calcBigestA(int[] arrayA, int[] arrayB) {
        int gcd = calcGcd(arrayA);
        
        for(int item : arrayB) {
            if(item % gcd == 0) {
                return 0;
            }
        }
        
        return gcd;
    }
    
    public int calcGcd(int[] arr) {
        int gcd = 1;
        
        for(int i=2; i<=arr[0]; i++) {
            boolean flag = true;
            
            for(int j=0; j<arr.length - 1; j++) {
                if(arr[j] % i != 0 || arr[j+1] % i != 0) {
                    flag = false;
                    break;
                }
            }
            
            if(flag) {
                gcd = i;
            }
        }
        
        return gcd;
    }
}

접근

최초에 배열을 정렬한 이유는 배열에서 가질 수 있는 최대 공약수는 정렬된 배열의 첫 번째 원소보다 작거나 같은 값으로 범위가 한정되기 때문입니다.
그러나, 이 방식은 브루트 포스를 통해 뒤에 위치한 원소들과 약수 관계인지 확인해야 했습니다.
- 이는 O(n * m)의 시간 복잡도를 가졌습니다. // n은 배열 최대 길이, m은 원소 최대 크기
- 조건
  - 1 ≤ arrayA의 길이 = arrayB의 길이 ≤ 500,000
  - 1 ≤ arrayA의 원소, arrayB의 원소 ≤ 100,000,000
음… 위 코드가 어떻게 통과했는지 모르겠네요…? 😅

개선 후

import java.util.*;

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        
        int gcdA = calcGcd(arrayA);
        int gcdB = calcGcd(arrayB);
        
        answer = Math.max(answer, calcBigestA(arrayA, arrayB, gcdA));
        answer = Math.max(answer, calcBigestA(arrayB, arrayA, gcdB));
        
        return answer;
    }
    
    public int calcGcd(int[] arr) {
        int gcdValue = arr[0];
        
        for(int i=1; i<arr.length; i++) {
            if(gcdValue == 1) {
                break;
            }
            
            gcdValue = gcd(gcdValue, arr[i]);
        }
        
        return gcdValue;
    }
    
    public int gcd(int a, int b) {
        if(a % b == 0) {
            return b;
        }
        
        return gcd(b, a % b);
    }
    
    public int calcBigestA(int[] arrayA, int[] arrayB, int gcd) {
        for(int item : arrayB) {
            if(item % gcd == 0) {
                return 0;
            }
        }
        
        return gcd;
    }
}