프로그래머스 [Lv. 2] 숫자 카드 나누기 {언어 : JavaScript} [2024.05.05 수정]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/135807?language=javascript

프로그래머스

정답 코드

function solution(arrayA, arrayB) {
    const n = arrayA.length;
    
    const gcd = (arr) => {
        let dp = Array(n).fill().map(() => 0);
        dp[0] = arr[0];
        for (let i = 1; i < n; i++) {
            let [n1, n2] = [dp[i-1], arr[i]];
            while (n1) {
                [n1, n2] = [n2%n1, n1];
            };
            dp[i] = n2;
        };
        return dp[n-1];
    };
    
    const gcdA = gcd(arrayA);
    const gcdB = gcd(arrayB);
    
    const isValid = (num, arr) => {
        let isNotDevidedUp = true;
        for (const a of arr) {
            if (a % num == 0) {
                isNotDevidedUp = false;
                break;
            };
        };
        return isNotDevidedUp
    };
    
    const resultA = isValid(gcdA, arrayB) ? gcdA : 0;
    const resultB = isValid(gcdB, arrayA) ? gcdB : 0;
    
    const answer = Math.max(resultA, resultB);
    return answer;
}

풀이 방법

1. 배열 A와 B의 최대공약수를 각각 구한다.
2. 구한 최대 공약수를 서로 다른 배열에서 나누어 떨어지는지 확인한다.
3. 나누어 떨어진다면 조건에 맞지 않으므로 0으로 바꾼다.
4. 구해준 결과값 A와 B 중 최대 값을 answer로 바꾼다.
5. answer를 반환한다.

느낀점

• 최대공약수를 구할 수 있으면 쉽게 풀 수 있는 문제

수정내역

• gbc => 최대공약수를 표현했는데 틀렸음
• gbc => gcd로 변경

 

https://sound-programming.tistory.com/175

최대공약수, 최소공배수, 유클리드 호제법 {언어: 자바스크립트}