문제
소수점 아래 숫자가 계속되지 않고 유한개인 소수를 유한소수라고 합니다. 분수를 소수로 고칠 때 유한소수로 나타낼 수 있는 분수인지 판별하려고 합니다. 유한소수가 되기 위한 분수의 조건은 다음과 같습니다.
- 기약분수로 나타내었을 때, 분모의 소인수가 2와 5만 존재해야 합니다.
두 정수 a와 b가 매개변수로 주어질 때, a/b가 유한소수이면 1을, 무한소수라면 2를 return하도록 solution 함수를 완성해주세요.
- 제한사항
- a, b는 정수
- 0 < a ≤ 1,000
- 0 < b ≤ 1,000
풀이
- 오답
처음에 이렇게 문제를 풀었더니 75점을 맞았다. 곰곰히 생각해 보니 기약분수를 만드는 과정에서 a가 b로 나누어지는 경우만 체크해서 생긴 문제라는 걸 알았다. 그게 b든 뭐든 최대공약수를 제대로 구해 기약분수를 만든 다음 2와 5만 존재하는지를 바르게 체크해야 했던 것!
class Solution {
public int solution(int a, int b) {
int answer = 2;
while(a % b == 0){
a /= b;
b /= b;
}
if(b % 2 == 0 || b % 5 == 0) answer = 1;
return answer;
}
}- 정답
그래서 다음과 같이 코드를 전개했다. 우선 최대공약수를 구했다. Math.min()을 통해 1에서부터 a와 b 둘 중 더 작은 수까지 루프를 돌며 a와 b 모두를 나누었을 때 딱 떨어지는지 체크했다. 이때, 가장 크게 나누어지는 수가 곧 최대공약수이므로 break;는 따로 하지 않았다.
그렇게 루프를 돌며 a와 b를 나눌 수 있는 가장 큰 수를 gcd에 대입 받은 뒤, 그 수로 분모인 b를 나누어 주었다. 어차피 유한소수 여부는 분모를 통해 결정되기 때문에 내가 처음에 코드를 짠 것처럼 a까지 나누어주고 그럴 필요가 없었음.
그렇게 최대공약수로 약분된 b를 while()을 이용해 각각 2와 5로 나눌 수 있을 때까지 나눈다. 이 역시 내가 처음에 코드를 짠 것처럼 2로 나누어지거나 5로 나누어질 수 있는지만 체크해서는 올바르게 풀 수 없는 부분이었다. (2로 나누어지거나 5로 나누어지지만 다른 수로도 나누어질 수 있음 = 유한소수가 아님)
마지막으로 2와 5로 나눌 수 있을 때까지 나눈 b가 1이면, 그것은 최대공약수로 약분한 b가 2와 5로만 이루어져있다는 뜻이 되므로 유한소수가 된다. 이를 변수를 따로 할당하지 않고 삼항 연산자를 통해 바로 return 하도록 했다.
class Solution {
public int solution(int a, int b) {
int gcd = 1;
for(int i=1; i<=Math.min(a, b); i++){
if(a % i == 0 && b % i == 0) gcd = i;
}
b /= gcd;
while(b % 2 == 0) b /= 2;
while(b % 5 == 0) b /= 5;
return (b == 1) ? 1 : 2;
}
}결과
