99클럽 코테 스터디 2일차 TIL + Java Algorithm

 

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL란? 'Today I Learned'약자로 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

문제

• 프로그래머스 - 숫자 카드 나누기(문제 링크)
• 유클리드 호제법 활용
• 최대공약수

 

문제 해결 과정

• 문제 해결을 위한 핵심 조건은 다음과 같습니다:
  1. 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a.
  2. 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a.
• 따라서, A와 B 배열이 있을 때, 하나의 배열의 최대공약수가 다른 배열의 원소들과 나누어지지 않는 경우를 찾으면 됩니다.

 

첫 번째 풀이 - 단계별로 작성

• 유클리드 호제법을 활용해 각각의 배열에 대한 최대공약수를 구합니다.
• 두 배열의 최대공약수가 같다면 0을 출력합니다.
• 각 배열의 최대공약수가 다른 배열의 원소들로 나누어지는지 판별하기 위해 boolean bIsDividedByA와 boolean aIsDividedByB 변수를 선언해 루프를 돌며 값을 변경합니다.
• 유클리드 호제법의 결과가 1이라면 1 이외의 다른 공약수는 없다는 것이므로, 플래그 변수를 활용해 각 상황에 맞게 정답을 반환합니다.

아래는 위의 논리를 단계별로 구현한 코드입니다.

class Solution {

    // 유클리드 호제법을 이용한 최대공약수 계산
    private static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    public static int solution(int[] arrayA, int[] arrayB) {
        int aGcd = arrayA[0];
        for (int i = 1; i < arrayA.length; i++) {
            aGcd = gcd(Math.max(aGcd, arrayA[i]), Math.min(aGcd, arrayA[i]));
        }

        int bGcd = arrayB[0];
        for (int i = 1; i < arrayB.length; i++) {
            bGcd = gcd(Math.max(bGcd, arrayB[i]), Math.min(bGcd, arrayB[i]));
        }

        if (aGcd == bGcd) {
            return 0;
        }

        boolean bIsDividedByA = false;
        if (aGcd != 1) {
            for (int num : arrayB) {
                if (num % aGcd == 0) {
                    bIsDividedByA = true;
                    break;
                }
            }
        }

        boolean AIsDividedByB = false;
        if (bGcd != 1) {
            for (int num : arrayA) {
                if (num % bGcd == 0) {
                    AIsDividedByB = true;
                    break;
                }
            }
        }

        // 둘다 서로 나눠지면 0 리턴
        if (bIsDividedByA && AIsDividedByB) {
            return 0;
        }
        // 둘다 서로 안나눠지면 큰 수 리턴
        if (!bIsDividedByA && !AIsDividedByB) {
            return Math.max(aGcd, bGcd);
        }
        // B가 A의 최대공약수로 나누어 지고 A는 B의 최대공약수로 나누어지지 않을때 B의 최대공약수가 1이 아닌 경우 
        if (bIsDividedByA && !AIsDividedByB) {
            return bGcd == 1 ? 0 : bGcd;
        }
        // A가 B의 최대공약수로 나누어 지고 B는 A의 최대공약수로 나누어지지 않을때 A의 최대공약수가 1이 아닌 경우
        return aGcd == 1 ? 0 : aGcd;
    }
}

 

두 번째 풀이 - 리팩터링을 통한 가독성 개선

• 같은 논리를 따르지만, 코드의 가독성을 높이기 위해 리팩터링을 수행했습니다.
• 주요 변경 사항
  • 메서드 분리 - 최대공약수를 구하는 로직과 배열 요소가 특정 값으로 나누어지는지 확인하는 로직을 별도 메서드로 분리.
  • 불필요한 조건 제거 - 최대공약수가 1인 경우를 처리하는 조건을 단순화.

아래는 리팩터링한 코드입니다.

import java.util.Arrays;

class Solution {

    // 유클리드 호제법을 이용한 최대공약수 계산
    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    // 배열의 최대공약수 계산
    private static int findGCD(int[] array) {
        return Arrays.stream(array)
							       .skip(1)
                     .reduce(array[0], (a, b) -> gcd(a, b));
    }

    // 특정 값으로 배열 요소가 나누어지는지 확인
    private static boolean isDivisibleBy(int divisor, int[] array) {
        return Arrays.stream(array)
                     .anyMatch(num -> num % divisor == 0);
    }

    public static int solution(int[] arrayA, int[] arrayB) {
        int gcdA = findGCD(arrayA);
        int gcdB = findGCD(arrayB);

        if (gcdA == gcdB) {
            return 0;
        }

        boolean bDividesA = isDivisibleBy(gcdA, arrayB);
        boolean aDividesB = isDivisibleBy(gcdB, arrayA);

        if (bDividesA && aDividesB) {
            return 0;
        }

        if (!bDividesA && !aDividesB) {
            return Math.max(gcdA, gcdB);
        }

        if (!bDividesA) {
            return gcdA;
        }

        if (!aDividesB) {
            return gcdB;
        }

        return 0;
    }
}

 

---

 

마무리하며

• 처음에는 문제 해결을 위해 직관적으로 코드를 작성했다면, 이후에는 코드의 가독성을 높이고 유지보수를 용이하게 하기 위해 리팩터링을 진행했습니다.
• 이러한 복기 과정을 반복하다 보면 문제 해결 능력뿐만 아니라, 더 나은 코드를 작성하는 역량을 키울 수 있을거라 생각합니다.