[프로그래머스/C++ 문제 풀이] Lv. 0 - 유한 소수 판별하기

문제 설명

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

• 기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 합니다.

두 정수 a와 b가 매개변수로 주어질 때, a/b가 유한소수이면 1을, 무한소수라면 2를 return하도록 solution 함수를 완성해주세요.

제한 사항

• a, b는 정수
• 0 < a ≤ 1,000
• 0 < b ≤ 1,000

입출력 예

a	b	result
7	20	1
11	22	1
12	21	2

 

입출력 예 #1

• 분수 7/20은 기약분수 입니다. 분모 20의 소인수가 2, 5 이기 때문에 유한소수입니다. 따라서 1을 return합니다.

입출력 예 #2

• 분수 11/22는 기약분수로 나타내면 1/2 입니다. 분모 2는 소인수가 2 뿐이기 때문에 유한소수 입니다. 따라서 1을 return합니다.

입출력 예 #3

• 분수 12/21는 기약분수로 나타내면 4/7 입니다. 분모 7은 소인수가 7 이므로 무한소수입니다. 따라서 2를 return합니다.

---

문제 풀이

이번 문제는 a / b를 기약분수로 나타내고, b의 소인수가 2나 5로만 구성되어 있는지를 판별하여 유한소수인지를 체크하는 문제입니다.

 

저는 2가지 단계를 거쳐 문제를 해결하게 되었습니다.

1. 기약분수 만들기 (최대 공약수를 찾아 분모에 나눠주기)
2. 분모를 소인수분해하기 (2와 5이외의 다른 값으로 나눠지는지 체크하기)

문제의 전체적인 난이도도 쉽고, "유한 소수"에 대한 뜻만 알고 있으면 간단하게 풀 수 있는 문제라고 생각합니다.

정답 코드

#include <string>
#include <vector>

using namespace std;

int solution(int a, int b) {
    int answer = 0;

    // 1. 기약분수 만들기

    // * 최대공약수 찾기
    int mxNum = 0;
    for (int i = 1; i <= (a < b? a : b); i++)
    {
        // 둘 다 나누어 떨어진다면 해당 숫자를 공약수로 저장
        if (a % i == 0 && b % i == 0)
        {
            mxNum = i;
        }
    }

    // * 찾은 최대 공약수를 분모(b)에 나눠주기
    b /= mxNum;

    // 2. 분모를 소인수 분해하기
    while (true)
    {
        // 2로 나누어 지는 경우 값 업데이트 하기
        if (b % 2 == 0)
        {
            b /= 2;
        }
        // 5로 나누어 지는 경우 값 업데이트 하기
        else if (b % 5 == 0)
        {
            b /= 5;
        }
        // 둘 다 안 나눠지는 경우 종료
        else
        {
            break;
        }
    }

    // 3. 결과 출력하기
    if (b == 1)
        answer = 1;
    else
        answer = 2;

    return answer;
}