[프로그래머스] '유한소수 판별하기' - Java

<문제 제시>

<문제설명>
소수점 아래 숫자가 계속되지 않고 유한개인 소수를 유한소수라고 합니다. 
분수를 소수로 고칠 때 유한소수로 나타낼 수 있는 분수인지 판별하려고 합니다. 
유한소수가 되기 위한 분수의 조건은 다음과 같습니다.

기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 합니다.
두 정수 a와 b가 매개변수로 주어질 때, 
a/b가 유한소수이면 1을, 무한소수라면 2를
return하도록 solution 함수를 완성해주세요.

<예시 입출력>

---

<문제 해결 과정>

문제에서 주어진 2와 5만을 소인수로 가져야하므로 a/b를 기본 토대로 해결해보고자 하였다.

Try 1) 

int answer = 1;
int[] fac = {};

List<Integer> save = new ArrayList<>();
// 소수는 2부터시작하므로 2로 초기화
int i = 2;

// n이 2보다 같거나 작아질때까지 반복
while(b >= 2) {
    if(b % i == 0) {
        // 굳이 리스트의 인덱슬르 붙이지 않아도 값만 추가해도된다는 사실을 알게됨
        save.add(i);
        // n을 업데이트해줌 (i로 나눈값)
        b /= i; 
    }

    // 조건에 해당하지 않을경우 2로나누는것이아닌 i를 증가시킨 값으로 업데이트 후 나눠줌
    else {
        i++;
    }
}

System.out.println(save);
fac = save.stream().distinct().mapToInt(Integer::intValue).toArray();

for(int k = 0; k < fac.length; k++) {
    if(fac[k] == 2 || fac[k] == 5) {
        answer = 1;
    }
    else answer = 2;
}

return answer;

테스트케이스 2번에서 통과하지 못하였다. (오답)

stream클래스를 이용해 중복을 제거하는 과정에서, '11' 이나 '22' 값을 넣었을때 22의 값이 2로 제거되어 fac에 담기는 것을 확인할 수 있었다.

Solution 1)

먼저 주어진 수를 newB라는 정수형 변수에 (큰 수 / 최대공약수) 형태로 대입한다.

// 큰 수를 최대공약수로 나눠 새로운 값 업데이트
int newB = b / gcd(a, b);

// 업데이트된 큰 수의 값이 1이 아니고, 
while (newB != 1) {
    // 2의 배수이면 2로 나눠서 재판별
    if (newB % 2 == 0) {
        newB /= 2;
    } 
    // 5의 배수이면 5로 나눠서 재판별
    else if (newB % 5 == 0) {
        newB /= 5;
    }
    // 이 모든것이 해당하지 않으면 2를 반환 (분모의 소인수가 2와 5가 아닌 경우)
    else {
        return 2;
    }
}

// 유한소수일 경우 기본적인 반환방법
return 1;

newB가 1이 아닐때까지 반복(while)한다.

2와 5의 배수인지 판별하기 위해 % 연산자를 사용하였고, 이 모든 조건이 해당하지 않을 경우는 무한소수이므로

2를 리턴한다.

최대공약수를구하는 GCD 함수를 이용하여 유한소수와 무한소수를 판별하고자하였다.

// 최대공약수를 구하는 함수 활용
public static int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

주어진 수 중 분자 = a, 분모 = b이므로 분모가 0이면 그대로 분자 a를 리턴하는 조건문과

그렇지 않을 경우(분모를 분자로 두고, 분모는 (분자 % 분모))한 값을 재귀호출 인자로 건넨다).

---

<전체코드>

import java.util.ArrayList;
import java.util.List;

// 분모의 소인수가 2와 5만 존재
public class finite_decimal {

	public static int solution(int a, int b) {
		
		// 큰 수를 최대공약수로 나눠 새로운 값 업데이트
        int newB = b / gcd(a, b);

        // 업데이트된 큰 수의 값이 1이 아니고, 
        while (newB != 1) {
        	// 2의 배수이면 2로 나눠서 재판별
        	if (newB % 2 == 0) {
            	newB /= 2;
            } 
        	// 5의 배수이면 5로 나눠서 재판별
        	else if (newB % 5 == 0) {
                newB /= 5;
            }
        	// 이 모든것이 해당하지 않으면 2를 반환 (분모의 소인수가 2와 5가 아닌 경우)
        	else {
                return 2;
            }
        }

        // 유한소수일 경우 기본적인 반환방법
        return 1;
    }

	// 최대공약수를 구하는 함수 활용
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
	
	public static void main(String[] args) {
		int a = 11;
		int b = 22;
		
		System.out.println(solution(a, b));
	}
}

ArrayList나 stream()클래스를 이용하지 않고서도 최대공약수를 구하는 GCD 함수를 이용해서 유한소수와

무한소수를 간단히 판별할 수 있었다.

---

최대공약수를 구하는 GCD함수의 경우 많은 알고리즘문제에서 활용되므로 충분히 익혀야겠다고 느꼈다.

---

문제링크)
https://school.programmers.co.kr/learn/courses/30/lessons/120878

프로그래머스