[C#][프로그래머스 >코딩테스트 입문] 유한소수 판별하기

프로그래머스 > 코딩테스트 연습 > 코딩테스트 입문 > 유한소수 판별하기

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

 

📒 문제

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

기약분수로 나타내었을 때, 분모의 소인수가 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합니다.

Hint

• 분자와 분모의 최대공약수로 약분하면 기약분수를 만들 수 있습니다.
• 정수도 유한소수로 분류합니다.

---

💻 소스코드

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int a, int b) {
        /*
            최대공약수로 나누면 기약분수
            최대공약수는 공통 약수 중 가장 큰거
            약수는 소인수분해로 구할 수 있음
        */
        
        int num = 1;
        
        // 최대공약수 구하기(a의 약수이면서 b의 약수인 수 중 가장 큰 수)
        for(int i = 1; i <= Math.Min(a,b); i++)
        {
            if((a % i == 0) && (b % i == 0)) num = i;
        }
        
        // 분모를 최대공약수로 나눠서 기약분수로
        b /= num;
        
        // 분모가 2와 5로만 이뤄졌는지 확인
        while(b%2 == 0) b /= 2;
        while(b%5 == 0) b /= 5;
        
        return b == 1 ? 1 : 2;
    }

 

※ 참고 사이트

소인수분해: https://kbhetrr.dev/blog/prime-factorization/
List 길이: https://codechacha.com/ko/csharp-length-of-list/

풀이: https://velog.io/@oaksusu/%EA%B8%B0%EC%B4%88-Lv.0-%EC%9C%A0%ED%95%9C%EC%86%8C%EC%88%98-%ED%8C%90%EB%B3%84%ED%95%98%EA%B8%B0

📝 풀이

유한소수인지 판단 하기 위해서는 기약분수로 나타냈을때, 분모의 소인수가 2와 5만 존재해야한다.

 

기약분수는 최대공약수로 나누면 알 수 있고

최대공약수는 공통의 약수 중 가장 큰 수이다.

 

그래서 약수 중 가장 큰 수를 구하고 분모를 최대 공약수로 나눠 기약분수로 만들어 준 다음 2 와 5로 나눌 수 있을때 까지 나눴을때 1이 되면 유한소수가 되고, 1 이외의 수가 나오면 2, 5 말고도 다른 소인수가 있다는 의미임으로 무한소수가 된다.

 

오답노트

밑의 내용은 오답이니 참고하지 마세요!

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int a, int b) {
        /*
            최대공약수로 나누면 기약분수
            최대공약수는 공통 약수 중 가장 큰거
            약수는 소인수분해로 구할 수 있음
        */
        
         int answer = 1;
         if(a%b == 0) return answer; // 정수인 경우
         if(b%a == 0){
             b /= a;
             a /= a;
         } //약분
      
      
         // 분자 소인수(prime factor)
         List<int> pfA = Factorization(a);
        
         // 분모 소인수(prime factor)
         List<int> pfB = Factorization(b);
      
         // 최대공약수(the greatest common denominator) 찾기
         int GCD = 1;
         for(int i = 0 ; i < pfA.Count ; i++){
             for(int j = 0 ; j < pfB.Count ; j++){
                 if(pfA[i] == pfB[j] && pfA[i] > GCD) GCD = pfA[i];
             }
         }
      
         // 기약분수로
         b /= GCD;
      
         // 유한소수 판단
         pfB = Factorization(b);
         for(int i = 0 ; i < pfB.Count ; i++)
         {
             answer = pfB[i] != 2 && pfB[i] != 5 ? 2 : 1;
             if(answer == 2) break;
         }

        return answer;
    }
    
    // 소인수분해 알고리즘
    private List<int> Factorization(int num){
        
        List<int> pf = new List<int>();
        for(int i = 2 ; i <= num ; i++)
        {
            while(num%i == 0) 
            {
                pf.Add(i);
                num /= i;
            }    
        }
             
        return pf;
    }
}

 

 [반례] 1, 30 -> 유한소수 판단 과정에서 2,5 이외 약수를 발견했지만 break하지않음

=> answer가 2가 되면 break

 [반례] 27, 27 -> 정수가 되는것을 판단하지 않음

=> if(a%b == 0) return answer;로 정수 판단

 [반례] 9, 18 -> 소인수분해 했을때 최대공약수를 제대로 찾지 못함

=> b%a == 0일 경우 각 분모, 분자에 a를 나눠 약분해서 해당 반례는 통과

 

하지만 25번 테스트가 계속 실패해서 반례를 더 이상 찾지못해서 해설을 참고했다.

내 풀이엔 필요 이상의 코드가 많았다. 간단한 코드로 해결할 수 있도록 연습해야겠다.

---

관련 내용

https://twd0622.tistory.com/8

[C# 문법] List메서드 모음