[Lv.0] 프로그래머스 - 유한소수 판별하기 : Java

프로그래머스

 

 

 

이해하기

처음 생각했던 로직은 다음과 같다.

• a와 b의 최대공약수를 찾는다.
• a와 b를 최대공약수로 각각 나누어준다.
• b의 소인수가 2와 5만 존재하는지 판단한다.

class Solution {
    public int solution(int a, int b) {
        int gcd = gcd(a, b);
        
        a /= gcd;
        b /= gcd;
        
        if (b % 2 == 0 || b % 5 == 0) {
            return 1;
        } else {
            return 2;
        }
    }
    
    public int gcd(int a, int b) {
        int gcd = 1;
        
        for (int i = 1; i <= a; i++) {
            if (a % i == 0 && b % i == 0) {
                gcd = i;
            }
        }
        
        return gcd;
    }
}

 

하지만 실패ㅠ 질문하기에서 반례를 좀 찾아보니 a = 15, b = 22 가 있어 테스트 케이스에 넣어보았다.

원래라면 22의 소인수는 11도 있기에 2가 나와야하는데 위 코드로는 1이 나왔다.

2나 5로 나누어지기만 하면 통과시켜버렸기 때문!

 

방법을 고민하다가 1을 제외한 약수를 List에 전부 담고, 2나 5로 나누어지는 약수는 List에서 지우기로 하였다.

만약 지우고도 List에 약수가 남아있다면 이는 2나 5로 나누어지지 않는 약수이니 2를 리턴한다.

List가 비었다면 1을 리턴한다.

 

 

문제풀이

import java.util.*;

class Solution {
    public int solution(int a, int b) {
        int gcd = gcd(a, b);
        b /= gcd;
        
        List<Integer> list = new ArrayList<>();
        for (int i = 2; i <= b; i++) {
            if (b % i == 0) {
                list.add(i);
            }
        }
        
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) % 2 == 0 || list.get(i) % 5 == 0) {
                list.remove(list.get(i));
                i--;
            }
        }
        
        if (list.size() == 0) {
            return 1;
        } else {
            return 2;
        }
    }
    
    // 유클리드 호제법
    public int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        
        return gcd(b, a % b);
    }
}