두 개의 정수 num1과 num2가 주어졌을 때, num1을 num2로 나눈 결과에서 소수점 이하 자릿수가 총 몇 개인지 계산하는 것이 이 글의 목표입니다.
예시
입력: num1 = 2, num2 = 5
출력: 자릿수는 1
설명: 2를 5로 나누면 2 ÷ 5 = 0.4이므로 소수점 이하 자릿수는 한 자리입니다. 따라서 결과는 1이 됩니다.
입력: num1 = 2, num2 = 0
출력: 부동 소수점 예외(Floating point exception) 발생 후 비정상 종료
설명: 어떤 수든 0으로 나누면 오류가 발생하며 프로그램이 비정상적으로 종료됩니다.
입력: num1 = 2, num2 = 3
출력: 무한대(Infinite)
설명: 2를 3으로 나누면 2 ÷ 3 = 0.666...처럼 소수점 이하가 무한히 반복되므로 자릿수를 셀 수 없습니다. 이 경우 "무한대"를 출력합니다.
프로그램에 사용된 접근 방식
두 변수 num1과 num2를 입력받습니다.
소수 자릿수를 저장할 count 변수를 선언하고 0으로 초기화합니다.
unordered_map 타입의 맵을 하나 생성합니다.
num1 % num2 != 0인 동안 반복문을 실행합니다.
반복문 내부에서 num1을 num1 % num2(나머지) 값으로 갱신합니다.
count 값을 1씩 증가시킵니다.
um.find(num1) != um.end() 조건을 만족하면, 즉 같은 나머지가 다시 등장해 순환이 시작되면 -1을 반환하여 무한 소수임을 알립니다.
반복문이 끝나면 count 값을 반환합니다.
최종 결과를 출력합니다.
여기서 unordered_map은 이미 한 번 등장했던 나머지를 기록하기 위해 사용됩니다. 나눗셈 과정에서 동일한 나머지가 반복해서 나타난다면 그 뒤로는 소수 자릿수가 같은 패턴으로 무한히 반복되므로, 이를 감지하면 더 이상 계산하지 않고 무한 소수로 판별할 수 있습니다.
또한 나머지의 종류는 최대 num2가지뿐이므로 이 알고리즘의 시간 복잡도는 대략 O(num2)이며, 반복 소수 여부까지 함께 판별할 수 있다는 장점이 있습니다.
예제 코드
#include <iostream>
#include <unordered_map>
using namespace std;
int countdigits(int x, int y){
int result = 0; // 결과를 저장할 변수
unordered_map<int, int> mymap;
// 나머지를 계산하며 소수 자릿수 카운트
while (x % y != 0){
x = x % y;
result++;
if (mymap.find(x) != mymap.end()){
return -1;
}
mymap[x] = 1;
x = x * 10;
}
return result;
}
int main(){
int res = countdigits(2, 5);
(res == -1) ? cout << "count is Infinity" : cout << "count is " << res;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
count is 1