프로그래머스 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. 문제 이해

• a / b 가 정수인 것 포함해서 기약분수로 만들었을 때 그게 유한소수인지 무한소수인지를 판별한다.
• input은 a,b 모두 10^3이지만 반복을 도는 상황은 아니라고 생각한다. 그래서 시간복잡도는 여유로움
• 최대공약수로 나누었을 때 분모에 2나 5가 아닌 다른 숫자가 있으면 무한 소수 아니면 유한 소수

2. 접근 방법

• 직관적으로 생각하기
  • a,b의 최대공약수를 구한다.
  • 최대공약수로 a와 b를 나눈다.
  • 분모를 소인수 분해해서 2나 5만 있는지 체크한다.
  • 조건에 맞게 1이나 2를 리턴한다.

3. 코드 설계

• 직관적으로 생각하기

  • 최대공약수 구하기

    const getGCD = (a, b) => {
        let gcd = 1
    
        for (let i = 2; i <= Math.min(a, b); i++) {
          if (a % i === 0 && b % i === 0) {
            gcd = i
          }
        }
    
        return gcd
      }
      const gcd = getGCD(a, b)

  • 최대공약수로 b만 나누기

    • let denoB = b / gcd

  • b를 최대공약수로 나눈 수를 소인수 분해해서 배열에 담는다.

    while (denoB >= 2) {
      if (denoB % divisor === 0) {
        result.push(divisor)
        denoB = denoB / divisor
      } else divisor++
    }

  • 배열에 2나 5만 있는지 확인하고 조건에 맞게 리턴한다.

    • return [...new Set(result)].every((v) => v === 2 || v === 5) ? 1 : 2

4. 코드 구현

function solution(a, b) {
  const getGCD = (a, b) => {
    let gcd = 1

    for (let i = 2; i <= Math.min(a, b); i++) {
      if (a % i === 0 && b % i === 0) {
        gcd = i
      }
    }

    return gcd
  }
  const gcd = getGCD(a, b)

  if (b / gcd === 1) {
    return 1
  }

  let denoB = b / gcd
  let result = []
  let divisor = 2

  while (denoB >= 2) {
    if (denoB % divisor === 0) {
      result.push(divisor)
      denoB = denoB / divisor
    } else divisor++
  }

  return [...new Set(result)].every((v) => v === 2 || v === 5) ? 1 : 2
}

다른 사람 풀이

function solution(a, b) {
    let n = 1;
    for (let i = 1; i <= Math.min(a,b); i++) {
        if (a%i===0 && b%i===0) n = i;
    }

    b/=n;
    while (b%2===0) b/=2;
    while (b%5===0) b/=5;

    return b === 1 ? 1 : 2;
}

회고

다른 사람 풀이를 보면 최대 공약수를 구하고 나처럼 소인수 분해할 필요도 없이 그냥 2와 5로 나누었을때 나머지가 0일때까지 해보고 그랬을때 b가 전부 나누어져서 1이 되면 1을 리턴하고 아니면 2를 리턴하게 했다. 전체적으로 이해하기도 쉬운 코드고 깔끔하다.. 나도 저런 코드를 작성하려고 노력하자!!

원래는 하루에 1시간 정도만 코딩테스트에 투자하려고 했는데, 답을 보지 않고 풀어보려고 노력하다보니까 길어지고 있다. 그래도 나쁘지 않게 생각한다.

생각하는 능력도 중요하다고 생각하기 때문에 알고리즘 문제 풀이에 시간이 조금 더 걸리는 부분은 괜찮다.