[프로그래머스] 유한소수 판별하기 (JAVA/ 자바)

 

 

 

생각한 방법

1. 기약분수 만들기
   • 유클리드 호제법을 이용해서 최대공약수로 나누기.
2. 분모 소인수 분해
   • 분모의 소인수가 2와 5만 있는지 확인하기.

 

[시도한 코드]

import java.util.*;

class Solution {
    public int solution(int a, int b) {
        int answer = 0;
        List<Integer> list = new ArrayList<>();
        int gcd = getGCD(a, b);
        b = b / gcd;
        
        // 소인수 리스트 구하기
        for(int i=2; i<=b; i++){
            if(b % i == 0){
               while(b % i == 0){
                    b /= i;
               }
                list.add(i);
            }
        }
        
        // 소인수가 2와 5인지 확인하기
        for(int i=0; i<list.size(); i++){
            if(list.get(i) == 2 || list.get(i) == 5){
                answer = 1;
            }
            if(list.get(i) != 2 && list.get(i) != 5){
                answer = 2;
            }
        }
        return answer;
    }
    
    // 최대공약수 로직
    private int getGCD(int n, int m){
        while(m != 0){
            int temp = n % m;
            n = m;
            m = temp;
        }
        return n;
    }

}

 

분모의 소인수가 2와 5만 존재할 경우 유한소수

분모의 소인수가 2와 5 외에도 존재할 경우 무한소수

 

위의 코드의 문제점

• 리스트 전체에 대해 적용되는 것이 아닌, 리스트에 존재하는 마지막 소인수에 의해 결과가 변경됨.

■ 분모가 30, 분자가 1인 경우

     분모 30의 소인수 : 2, 3, 5
     list = [2, 3, 5]

// 소인수가 2와 5인지 확인하기
for(int i=0; i<list.size(); i++){
    if(list.get(i) == 2 || list.get(i) == 5){
        answer = 1;
    }
    if(list.get(i) != 2 && list.get(i) != 5){
        answer = 2;
    }
}

• i = 0 일 경우 2 → answer = 1
• i = 1 일 경우 3 → answer = 2
• i = 0 일 경우 2 → answer = 1

마지막에 다시 1로 덮어쓰게 되기 때문에 무한소수임에도 유한소수가 되어버리는 문제 발생.

 

 

[최종 코드]

import java.util.*;

class Solution {
    public int solution(int a, int b) {
        int answer = 0;
        int gcd = getGCD(a, b);
        a = a / gcd;
        b = b / gcd;
        
        // 분모를 2로 나누기
        while(b % 2 == 0){
            b /= 2;
        }
        
        // 분모를 5로 나누기
        while(b % 5 == 0){
            b /= 5;
        }
        
        if(b == 1){
            answer = 1;
        }
        if(b != 1){
            answer = 2;
        }
        return answer;
    }
    
    private int getGCD(int n, int m){
        while(m != 0){
            int temp = n % m;
            n = m;
            m = temp;
        }
        return n;
    }
}

 

최종적으로 해결한 방법

 

최대공약수를 구한 뒤, 분자와 분모를 최대공약수로 나누어 기약분수로 바꾼다.

분모가 2로 나누어떨어지지 않을 때까지 2로 나눈 뒤, 5로 나누어떨어지지 않을 때까지 5로 나눈다.

 

분모가 1이 되었을 경우 → 소인수가 2와 5뿐이므로 유한소수. (1반환)

분모가 1이 되지않았을 경우 → 2와 5 이외의 소인수가 남아있으므로 무한소수. (2반환)