[프로그래머스/C++] 유한소수 판별하기

0. 문제

풀이한 문제 - 유한소수 판별하기 (프로그래머스 입문 / Lv . 0 / 73%)

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

프로그래머스

 

1. 테스트 케이스 분석

테스트 케이스를 분석하면 다음과 같다

문제에는 표 상단의 세 개만 제시되어 있었지만

문제 풀이 시 고려해야하는 예외 사항들을 추가해서 풀었다

 

일단 기약분수가 아닌 기약분수로 만들어야 

분모에 2 또는 5만 있는지 확인할 수 있기 때문에

기약분수로 만들기 위해 필요한 GCD (최대공약수)부터 구했다

 

당연한 이야기지만 혹시 놓쳤을 사람들을 위해

테스트 케이스를 분석한 위 사진을 확인해보면

기약분수는 GCD = 1 임을 알 수 있다

 

2. 코드 및 풀이

GCD는 분수의 분자와 분모를 모두 나누었을 때 나누어 떨어지는 수이다

 

i가 1일 때부터 분자와 분모 중 작은 수가 될 때까지 반복하여

GCD를 찾는데 이때 조건에 만족하는 더 큰 값을 찾으면 갱신되는 구조다

 

GCD 를 찾은 후에는

입력 받은 a, b를 GCD로 나눠서

기약분수로 만든다

 

GCD가 1인 경우는 굳이 의미 없으니 제외했다

 

여기까지 너무 순조로웠다

기약분수의 분모가 2 또는 5만 존재하면

유한소수로 나타낼 수 있기 때문에

분모가 2 또는 5로 나누어 떨어지는 조건만

확인하면 된다고 생각했기 때문이다

 

b % 2 == 0 || b % 5 == 0 의 조건을 입력하면

분모에 2 또는 5가 있기만 하면 참의 값을 출력하므로

 

위의 테스트 케이스처럼 3이나 7을 포함하더라도

참으로 계산된다

 

따라서 분모에 2 또는 5가 아닌 숫자가 있는 경우를

필터링 해줘야 한다

 

여러 가지 방법이 있겠지만

나는 분모를 계속 나누는 방식을 채택했다

 

분모가 2 또는 5로 나누었을 때

나누어 떨어지는 경우는 나눠서 b를 새 값으로 갱신했고

나누어 떨어지지 않는 경우가 되면 탈출하도록 했다

 

반복문은 b가 1이 되거나

2 또는 5의 배수가 아닌 수가 되면 탈출하게 되므로

 

탈출할 때 최종 갱신된 b값이

1이면 유한소수가 가능하므로 1을 리턴하고

1이 아니면 2 또는 5가 아닌 수가 분모에 포함된 것이므로

2를 리턴하도록 했다

 

 

해당 게시글에 사용된 PPT 이미지는

모두 직접 제작했습니다