최대공약수와 최소공배수

문제

두 수를 입력받아 최대공약수와 최소공배수를 배열로 반환하는 문제. (n, m은 1 ≤ x ≤ 1,000,000)

처음 짠 코드와 문제점

class Solution {
    public static int gcd(int n, int m){
        int remainder = 0;
        while(m%n>=0){
            if(m%n!=0){
                remainder=m%n;
                m=n;
                n=remainder;
            }else{
                remainder = n;
                break;
            }
        }
        return remainder;
    }

    public static int lcm(int n, int m, int gcdNum){
        int lcmNum=(n*m)/gcdNum;
        return lcmNum;
    }

    public int[] solution(int n, int m) {
        int gcdNum=gcd(n,m);
        int lcmNum=lcm(n,m,gcdNum);
        return new int[]{gcdNum, lcmNum};
    }
}

주어진 예제(3,12 / 2,5)는 통과하지만 두 가지를 놓치고 있었다.

1) while(m%n>=0) 조건이 사실상 의미가 없었다

n, m이 자연수(1 이상)이기 때문에 m%n은 항상 0 이상이다. 즉 이 while 조건은 항상 참이라서, 실제로 루프를 끝내는 건 조건식이 아니라 안에 있는 break였다. 조건만 보고는 "언제 끝나는 반복문인지" 전혀 알 수 없는 코드였던 것.

→ break를 지우면 어떻게 될지 트레이스해봤는데, m%n==0이 된 뒤에도 m, n이 더 이상 바뀌지 않으니 같은 나머지 연산을 무한히 반복하는 무한루프가 된다는 걸 확인했다.

2) n*m에서 정수 오버플로우

n, m이 최대 100만까지 가능한데, 서로소인 두 큰 수(예: 999983, 999979)를 곱하면 결과가 약 10^12로 int 최댓값(약 21억)을 훌쩍 넘는다. (n*m)/gcdNum처럼 곱셈을 그대로 int로 계산하면 나누기 전에 이미 오버플로우가 나버린다.

여기서 헷갈렸던 부분: long으로 결과를 받으면 해결될 줄 알았는데, 아래처럼 캐스팅 위치가 잘못되면 여전히 깨진다.

long multiply = (long) m * n;   // OK, 곱셈 자체는 long 정밀도
int lcmNum = (int)multiply/gcdNum;  // 문제! 캐스트가 나눗셈보다 우선순위가 높아서
                                     // (int)multiply 를 먼저 계산 → 여기서 이미 잘림

자바 연산자 우선순위상 캐스트((int))가 /보다 먼저 적용되기 때문에, 괄호 없이 쓰면 나누기 전에 int로 캐스팅해버려서 오버플로우 방지 효과가 사라진다.

고친 과정

gcd 리팩터링: 원래 if(m%n==0) return n;으로 특수 케이스를 따로 처리하고 그 아래 while로 일반 케이스를 처리했는데, 같은 나머지 연산을 두 번 검사하는 중복이 있었다. gcdNum의 초기값을 n으로 잡아두면, while 조건이 처음부터 거짓이어도(=바로 나누어떨어지는 경우) 초기값 n이 그대로 반환되어 if문 없이도 같은 결과가 나온다.

public static int gcd(int n, int m){
    int gcdNum = n;
    while(m%n!=0){
        int remainder = m%n;
        m = n;
        n = remainder;
        gcdNum = remainder;
    }
    return gcdNum;
}

lcm 오버플로우 수정: 곱셈은 (long) m * n으로 long 정밀도로 계산하고, 나눗셈까지 long 상태에서 끝낸 뒤에 마지막에 결과만 int로 캐스팅했다.

public static int lcm(int n, int m, int gcdNum){
    long multiply = (long) m * n;
    int lcmNum = (int)(multiply/gcdNum);  // 나눗셈을 먼저, 캐스팅은 마지막에
    return lcmNum;
}

최종 코드

class Solution {
    public static int gcd(int n, int m){
        int gcdNum = n;
        while(m%n!=0){
            int remainder = m%n;
            m = n;
            n = remainder;
            gcdNum = remainder;
        }
        return gcdNum;
    }

    public static int lcm(int n, int m, int gcdNum){
        long multiply = (long) m * n;
        int lcmNum = (int)(multiply/gcdNum);
        return lcmNum;
    }

    public int[] solution(int n, int m) {
        int gcdNum = gcd(n,m);
        int lcmNum = lcm(n,m,gcdNum);
        return new int[]{gcdNum, lcmNum};
    }
}

느낀 점

• 조건문을 짤 때 "이 조건이 실제로 거짓이 될 수 있는가"를 항상 확인해야 한다. 항상 참인 조건은 코드를 읽는 사람(미래의 나 포함)을 헷갈리게 만든다.
• 곱셈이 들어가는 자리는 입력 범위의 최댓값 기준으로 오버플로우 여부를 계산해보는 습관이 필요하다.
• long으로 바꾼다고 끝이 아니라, 어느 시점에 캐스팅/연산이 일어나는지(연산자 우선순위)까지 봐야 진짜 오버플로우를 막을 수 있다.
• 특수 케이스를 별도 if로 분기하기보다, 변수의 초기값을 잘 잡으면 분기 없이 일반 로직 하나로 통합할 수 있는 경우가 있다.