[알고리즘문제풀기] 유한소수 판별하기

silver

Feb 01, 2025

Contents

문제 내가 작성한 정답 - 유클리드 호제법 참고

문제

school.programmers.co.kr

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

내가 작성한 정답 - 유클리드 호제법 참고


import java.util.*;

class Solution {
    public int solution(int a, int b) {
        // 최대공약수 구하기
        int gcd = findGCD(a, b);
        
        // a와 b를 약분
        a /= gcd;
        b /= gcd;

        // b의 소인수가 2와 5만 존재하는지 확인
        while (b % 2 == 0) {
            b /= 2; // 2로 나누기
        }
        while (b % 5 == 0) {
            b /= 5; // 5로 나누기
        }

        // b가 1이면 유한소수, 아니면 무한소수
        return (b == 1) ? 1 : 2;
    }

    // 최대공약수 구하기
    private int findGCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

💡

유클리드 호제법


public class EuclideanAlgorithm {
    // 최대공약수 계산 메서드
    public static int gcd(int a, int b) {
        while (b != 0) { // b가 0이 아닐 때까지 반복
            int temp = b; // b의 값을 temp에 저장
            b = a % b; // a를 b로 나눈 나머지를 b에 저장
            a = temp; // temp의 값을 a에 저장
        }
        return a; // a가 최대공약수
    }
    
    // 최소공배수 계산 메서드
    public static int lcm(int a, int b) {
        return Math.abs(a * b) / gcd(a, b); // LCM 계산
    }  
}


    // 최대공약수 계산 메서드
    public static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b); // 삼항 연산자를 사용한 재귀적 호출
    }

    // 최소공배수 계산 메서드
    public static int lcm(int a, int b) {
        return (a != 0 && b != 0) ? Math.abs(a * b) / gcd(a, b) : 0; // 삼항 연산자를 사용하여 0 체크
    }

See more posts

[알고리즘문제풀기] 유한소수 판별하기

문제

내가 작성한 정답 - 유클리드 호제법 참고

유클리드 호제법

More articles

[알고리즘문제풀기] 문자열 밀기

[SQL문제풀기] 중성화 여부 파악하기

[SQL문제풀기] 이름에 el이 들어가는 동물 찾기

[알고리즘문제풀기] 저주의 숫자 3