[프로그래머스] 유한소수 판별하기(유클리드호제법, 소인수분해)

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

프로그래머스

---

---

문제 푼 코드

package programmers.pr2023.Lv0.February;

import java.util.HashSet;
import java.util.Iterator;

public class Lv0_유한소수판별하기_20230227 {
    class Solution {
        public int solution(int a, int b) {
            // 유한소수라면 1, 무한소수라면 2(유한소수 조건 : 분모의 소인수가 2와 5만 존재)
            // 정수도 유한소수로 판별
            int answer = 1;
            
            if(a == b) return 1; // 같다면 정수이므로 유한소수
            if(b == 1) return 1; // 분모가 1이라면 유한소수

            // 기약분수 나타내기(유클리드호제법)
            // a > b 일때, r = a%b, a = b, b = r; b가 0이 될 때의 a가 최대공약수
            if(a > b) {
                int r = 0;
                int x = a;
                int y = b;
                while(y != 0) {
                    r = x % y;
                    x = y;
                    y = r;
                }

                a = a / x;
                b = b / x;

                // 분모가 1이면 유한소수
                if(b == 1) return 1;
            }

            if(b > a) {
                int r = 0;
                int x = b;
                int y = a;
                while(y != 0) {
                    r = x % y;
                    x = y;
                    y = r;
                }

                a = a / x;
                b = b / x;

                // 분모가 1이면 유한소수
                if(b == 1) return 1;
            }
            
            // 방법1) 소인수분해
            HashSet<Integer> set = new HashSet<>();
            int k = 2;
            int n = b;
            while(k <= n) {
                if(n % k == 0) {
                    set.add(k);
                    n = n/k;
                } else {
                    k++;
                }
            }

            Iterator<Integer> iter = set.iterator();
            while(iter.hasNext()) {
                int temp = iter.next();
                if(!(temp == 2 || temp == 5)) {
                    return 2;
                }
            }

            return answer;
        }
    }
}

힌트를 보고 유클리드호제법을 사용해서 최대공약수를 구해 기약분수로 만들고 분모를 소인수분해하여 2,5외에 다른 값이 있으면 2를 리턴하도록 했었는데 테스트 케이스에서 계속 실패..

이유가 뭘까 반례를 찾다가 정수인 경우에도 유한소수로 판별하기 위해 분자와 분모가 같으면 1을 리턴, 분모가 1일 경우 정수이므로 1을 리턴하도록 수정했다.

그래도 테스트 케이스 일부분이 실패..

유클리드호제법을 사용할 때 a > b라는 조건이 있는데 꼭 분모가 크다라는 법은 없으니 반대의 경우도 유클리드호제법을 사용하도록 조건을 추가하였고 각 분기의 유클리드 호제법을 사용한 뒤 분모가 1인 경우에는 유한소수이기 때문에 1을 리턴하도록 하였다.

 

결과는 모든 테스트 케이스를 통과!!

 

레벨0 문제라면서.. 어려웠고.. 생각할 게 너무 많았다ㅠㅠ