Java로 양의 유리수 생성하기 – 효율적인 알고리즘과 구현 예제

유리수란 무엇인가?

유리수(Rational Number)란 p/q 형태로 표현할 수 있는 수를 말합니다. 이때 p와 q는 모두 정수여야 하며, 분모 q는 0이 아니어야 한다는 조건이 있습니다.

양의 유리수는 최종 값이 양수가 되는 유리수를 의미합니다. 이를 위해서는 분자 p와 분모 q가 둘 다 양수이거나, 둘 다 음수여야 합니다.

이 문제에서는 주어진 수 n까지의 양의 유리수를 생성해야 합니다. 즉, 1부터 n 사이에 존재하는 유한 개수의 양의 유리수를 찾아야 하며, 이를 위해 1 ≤ p ≤ n, 1 ≤ q ≤ n을 만족하는 모든 조합을 생성하게 됩니다.

문제 이해하기

개념을 더 명확히 이해하기 위해 예시를 살펴보겠습니다.

입력 : 3
출력 : 1, 1/2, 1/3, 2, 2/3, 3/2, 3

설명 − 이 예제에서는 분자 p와 분모 q에 대해 1부터 3 사이의 모든 값을 고려합니다.

알고리즘 접근 방식

이 알고리즘은 집합(Set) 자료구조를 활용하여 최적의 방식으로 필요한 조합을 생성합니다. 집합은 매핑이 가능하며, n 대 n 형태의 매핑, 즉 첫 번째 집합의 각 값을 두 번째 집합의 값과 짝지어 필요한 쌍(pair)을 만들어낼 수 있습니다. 양수 값들로 이루어진 두 집합을 매핑하여 해답을 도출하는 방식입니다.

예를 들어 다음과 같은 쌍들을 생각해볼 수 있습니다.

(1,1) , (1,2) , (1,3)
(2,1) , (2,2) , (2,3)
(3,1) , (3,2) , (3,3)

이 값들을 역 L자(inverted L-shape) 순회 방식으로 재배열하면 다음과 같습니다.

(1,1)
(1,2) , (2,2) , (2,1)
(1,3) , (2,3) , (3,3) , (3,2) , (3,1)

쉼표를 나눗셈 기호(/)로 바꾸면 실제로 생성되는 양의 유리수 값임을 확인할 수 있습니다.

1/1
1/2 , 2/2 , 2/1
1/3 , 2/3 , 3/3 , 3/2 , 3/1

그런데 1/1, 2/2, 3/3처럼 서로 같은 값을 가리키는 중복 항목들이 존재합니다. 이러한 중복은 최대공약수(GCD)를 이용해 제거할 수 있습니다. 분자와 분모의 최대공약수가 1인 경우, 즉 기약분수인 경우만 결과 목록에 추가하면 중복 없는 유리수 목록을 얻을 수 있습니다.

Java 구현 예제

import java.util.ArrayList;
import java.util.List;
class PositiveRational {
    private static class PositiveRationalNumber {
        private int numerator;
        private int denominator;
        public PositiveRationalNumber(int numerator, int denominator){
            this.numerator = numerator;
            this.denominator = denominator;
        }
        @Override
        public String toString(){
            if (denominator == 1) {
                return Integer.toString(numerator);
            } else {
                return Integer.toString(numerator) + '/' +
                Integer.toString(denominator);
            }
        }
    }
    private static int gcd(int num1, int num2){
        int n1 = num1;
        int n2 = num2;
        while (n1 != n2) {
            if (n1 > n2)
                n1 -= n2;
            else
                n2 -= n1;
        }
        return n1;
    }
    private static List<PositiveRationalNumber> generate(int n){
        List<PositiveRationalNumber> list = new ArrayList<>();
        if (n > 1) {
            PositiveRationalNumber rational = new PositiveRationalNumber(1, 1);
            list.add(rational);
        }
        for (int loop = 1; loop <= n; loop++) {
            int jump = 1;
            if (loop % 2 == 0)
                jump = 2;
            else
                jump = 1;
            for (int row = 1; row <= loop - 1; row += jump) {
                if (gcd(row, loop) == 1) {
                    PositiveRationalNumber rational = new PositiveRationalNumber(row, loop);
                    list.add(rational);
                }
            }
            for (int col = loop - 1; col >= 1; col -= jump) {
                if (gcd(col, loop) == 1) {
                    PositiveRationalNumber rational = new PositiveRationalNumber(loop, col);
                    list.add(rational);
                }
            }
        }
        return list;
    }
    public static void main(String[] args){
        List<PositiveRationalNumber>rationals = generate(5);
        System.out.println(rationals.stream().
        map(PositiveRationalNumber::toString).
        reduce((x, y) -> x + ", " + y).get());
    }
}

코드 설명

PositiveRationalNumber 클래스 − 분자(numerator)와 분모(denominator)를 저장하는 내부 클래스로, toString() 메서드를 통해 분모가 1일 때는 정수만, 그 외에는 '분자/분모' 형태로 출력합니다.
gcd() 메서드 − 두 수의 최대공약수를 유클리드 호제법 방식으로 계산하여, 최대공약수가 1인 기약분수만 걸러내는 데 사용됩니다.
generate() 메서드 − 역 L자 순회 방식으로 1부터 n까지 반복하면서 각 단계에서 행(row)과 열(col)을 순회하고, 최대공약수 검증을 통과한 유리수만 리스트에 추가합니다.

실행 결과

1, 1/2, 2, 1/3, 2/3, 3/2, 3, 1/4, 3/4, 4/3, 4, 1/5, 2/5, 3/5, 4/5, 5/4, 5/3, 5/2, 5

위 출력에서 볼 수 있듯이, n=5인 경우 1부터 5 사이의 모든 양의 유리수가 중복 없이 오름차순 분모 기준으로 정렬되어 생성됩니다. 이 알고리즘은 역 L자 순회 패턴과 GCD 기반 중복 제거를 결합하여 효율적으로 원하는 결과를 도출합니다.