C++에서 유리수를 소수 형태로 표현하는 프로그램 (반복 소수 처리)

분자(numerator)와 분모(denominator)라는 두 개의 숫자가 있고, 이 두 수가 분자 / 분모 형태의 유리수를 나타낸다고 가정해 봅시다. 이 유리수를 소수(decimal) 문자열 형태로 변환해야 하며, 만약 순환하는 자릿수(반복되는 숫자)가 있다면 해당 부분을 괄호로 묶어서 표시해야 합니다.

예를 들어, 분자 = 164, 분모 = 3이 입력으로 주어지면 출력은 "54.(6)"이 됩니다. 즉, 164 ÷ 3 = 54.6666...이므로 무한히 반복되는 '6'을 괄호로 감싸 표현하는 것입니다.

해결 접근 방법

이 문제는 실제 나눗셈(long division) 과정을 그대로 시뮬레이션하면 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

나머지가 같은 값으로 두 번 등장하면, 그 지점부터 소수 부분이 순환한다는 의미입니다. 따라서 각 나머지 값을 맵(map)에 기록하여 순환 시작 위치를 파악합니다.

알고리즘 단계

분자가 0이면 결과도 항상 0이므로 "0"을 반환합니다.
결과를 저장할 배열 ans를 정의합니다.
부호가 음수인 경우(분자와 분모 중 하나만 음수인 경우) ans에 '-'를 추가합니다.
divisor := |분자|, dividend := |분모|로 설정합니다.
remainder := divisor mod dividend 로 초기 나머지를 구합니다.
x := (divisor / dividend)의 몫을 문자열로 변환한 후, 각 자릿수를 ans에 추가합니다.
나머지가 0이라면 나누어떨어지는 경우이므로 ans를 문자열로 반환합니다.
나머지가 남아 있다면 ans에 '.'(소수점)을 추가합니다.
순환 여부 확인용 맵 m을 정의하고, remainder가 0이 될 때까지 다음을 반복합니다.
- 현재 remainder가 이미 맵 m에 존재하면 → 순환이 시작된 위치(ans.begin() + m[remainder])에 '('를 삽입하고 끝에 ')'를 추가한 뒤 반복을 종료합니다.
- 존재하지 않으면 → m[remainder]에 현재 ans의 크기를 기록하고, remainder에 10을 곱한 뒤 몫(remainder / dividend)의 자릿수를 ans에 추가하고, remainder를 dividend로 나눈 나머지로 갱신합니다.
최종적으로 ans를 문자열로 변환하여 반환합니다.

C++ 구현 예제

아래 구현 코드를 통해 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string solve(int numerator, int denominator) {
      if (numerator == 0)
         return "0";
      vector<char> ans;
      if (numerator < 0 && denominator > 0 || numerator > 0 && denominator < 0)
         ans.push_back('-');
      long divisor = labs(numerator);
      long dividend = labs(denominator);
      long remainder = divisor % dividend;
      string x = to_string(divisor / dividend);
      for (int i = 0; i < x.size(); i++) {
         ans.push_back(x[i]);
      }
      if (remainder == 0) {
         return string(ans.begin(), ans.end());
      }
      ans.push_back('.');
      map<int, int> m;
      while (remainder != 0) {
         if (m.find(remainder) != m.end()) {
            ans.insert(ans.begin() + m[remainder], '(');
            ans.push_back(')');
            break;
         } else {
            m[remainder] = ans.size();
            remainder *= 10;
            ans.push_back((remainder / dividend) + '0');
            remainder %= dividend;
         }
      }
      return string(ans.begin(), ans.end());
   }
};
string solve(int numerator, int denominator) {
   return (new Solution())->solve(numerator, denominator);
}
int main() {
   cout << solve(164, 3);
}

입력

164, 3

출력

54.(6)

동작 원리 요약

위 코드는 다음과 같은 흐름으로 동작합니다.

부호 처리: 분자와 분모의 부호가 서로 다르면 결과는 음수이므로 '-'를 먼저 붙입니다.
정수 부분 계산: 절댓값 기준으로 나눗셈을 수행해 정수 부분을 먼저 문자열에 넣습니다.
소수 부분 계산: 나머지에 10을 곱하며 한 자릿수씩 계산합니다. 이때 나머지가 반복되면 순환 소수임을 알 수 있습니다.
순환 구간 표시: 맵에 저장된 위치를 활용해 순환이 시작되는 지점에 '('를 삽입하고 마지막에 ')'를 붙여 완성합니다.

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도 역시 최악의 경우 O(n)입니다(n은 소수점 이하 자릿수). 나머지의 종류는 분모보다 작은 유한 개이므로 반드시 순환이 발생하거나 나누어떨어지게 되어 프로그램이 종료됩니다.