Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 분수를 소수 문자열로 변환하기: 반복 소수 괄호 표기법 완벽 가이드

문제 개요

분자(numerator)와 분모(denominator)를 나타내는 두 개의 정수가 주어졌을 때, 이 분수를 문자열 형태의 소수로 변환하는 프로그램을 작성해야 합니다. 이때 소수 부분이 무한히 반복된다면, 반복되는 부분을 괄호로 묶어 표현해야 합니다.

예를 들어 분자가 2이고 분모가 3이라면, 2 ÷ 3 = 0.6666...이므로 출력 결과는 "0.(6)"이 됩니다.

해결 전략

이 문제는 우리가 손으로 나눗셈을 계산하는 과정을 그대로 코드로 옮기는 방식으로 해결할 수 있습니다. 핵심 아이디어는 나머지(remainder)를 추적하는 것입니다. 나눗셈 도중 동일한 나머지가 다시 등장하면, 그 지점부터 소수 숫자가 반복된다는 의미이므로 해당 위치에 여는 괄호 '('를 삽입하고 끝에 닫는 괄호 ')'를 추가하면 됩니다.

구체적인 알고리즘은 다음과 같습니다.

  • 분자가 0이면 즉시 "0"을 반환합니다.
  • 결과를 저장할 배열 ans를 선언합니다.
  • 부호가 음수인 경우(분자와 분모 중 하나만 음수) ans 배열에 '-' 기호를 삽입합니다.
  • divisor := |분자|, dividend := |분모|로 설정하고, remainder := divisor mod dividend로 초기화합니다.
  • x := 정수 몫(divisor / dividend)을 문자열로 변환한 값으로 두고, 각 문자를 ans 배열에 삽입합니다.
  • 나머지가 0이면 나누어 떨어진 것이므로 ans 배열을 문자열로 반환합니다.
  • 나누어 떨어지지 않으면 ans에 소수점 '.'을 삽입합니다.
  • 나머지 위치를 기록할 맵(map) m을 선언합니다.
  • 나머지가 0이 아닌 동안 다음을 반복합니다.
    • 현재 나머지가 맵 m에 이미 존재한다면:
      • ans 배열의 m[remainder] 인덱스 위치에 여는 괄호 '('를 삽입합니다.
      • ans 배열 끝에 닫는 괄호 ')'를 추가합니다.
      • 반복문을 종료합니다.
    • 존재하지 않는다면:
      • m[remainder] := 현재 ans 배열의 크기를 기록합니다.
      • remainder := remainder × 10으로 갱신합니다.
      • (remainder / dividend)의 값을 문자로 변환하여 ans에 삽입합니다.
      • remainder := remainder mod dividend로 갱신합니다.
  • 최종적으로 ans 배열을 문자열로 변환하여 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 구현을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string fractionToDecimal(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());
    }
};
main(){
    Solution ob;
    cout << ((ob.fractionToDecimal(100,6)));
}

입력

100
6

출력

16.(6)

동작 원리 상세 분석

위 예제에서 100 ÷ 6의 계산 과정을 살펴보면 다음과 같습니다.

  • 정수 몫은 16이고, 초기 나머지는 100 mod 6 = 4입니다.
  • 소수점을 추가한 후 나머지 4를 기록하고, 4 × 10 = 40을 6으로 나누면 몫은 6, 나머지는 다시 4가 됩니다.
  • 나머지 4가 이미 맵에 존재하므로, 처음 4가 기록된 위치(소수점 바로 뒤)에 '('를 삽입하고 마지막에 ')'를 붙여 "16.(6)"이라는 결과를 얻습니다.

주요 포인트 정리

  • 오버플로우 방지: INT_MIN 같은 극단적인 값의 절댓값을 구할 때 int 범위를 초과할 수 있으므로 long 타입과 labs() 함수를 사용하는 것이 안전합니다.
  • 반복 검출 메커니즘: 나머지는 항상 분모보다 작으므로, 서로 다른 나머지 값의 개수는 유한합니다. 따라서 동일한 나머지가 재등장하면 반드시 순환이 발생하며, 알고리즘은 무한 루프에 빠지지 않습니다.
  • 괄호 삽입 위치: 맵에는 나머지가 처음 등장했을 때의 ans 배열 크기(인덱스)를 저장하므로, 반복 시작 지점에 정확하게 괄호를 삽입할 수 있습니다.

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로, n은 결과 문자열의 길이입니다. 나눗셈의 성질상 소수부의 길이는 최대 분모 - 1까지이므로 매우 효율적으로 동작합니다.