[BOJ 5376] 소수를 분수로

5376번: 소수를 분수로

문제 분석

• 제한시간 1초 : 약 1억 연산
• 소수점 아래의 수의 범위 최대 15자리 : 소수점아래의 숫자들을 한 정수형 변수에 담을 수 없다.
• 결과 값을 기약분수로 바꾸는 방법 : 분모와 분자의 최대 공약수를 구해 분모와 분자를 최대공약수로 나눈다.
• 비순환소수를 분수로 바꾸는 방법 : 10^(소수점 아래의 자릿수) * 해당 소수 / 10^(소수점 아래의 자릿수)
• 순환소수를 분수로 바꾸는 방법 :
  10^(첫 순환부까지의 자릿수) * 첫 순환부까지의 수 - 10^(첫 순환부전까지의 자릿수) * 첫 순환부 전까지의 수
  ÷
  10^(첫 순환부까지의 자릿수) - 10^(첫 순환부전까지의 자릿수)
  EX)

• 보기에 직관적인 방법 :
  (비순환부 부터 순환부) - (비순환부) -> 분자
  순환부에 맨 뒤에서부터 9를 써주다가 , 비순환부 가 나오면 0을 쓴다. -> 분모

풀이 방식

• 비순환소수 :
  소수점 아래의 수들을 정수형으로 바꾼다.
  빈 문자열에 '1'을 추가한다.
  문자열에 소수점 아래의 자릿수를 만큼 '0'을 추가한다.
  문자열을 정수형으로 바꾼다.
  정수로 바뀐 값 / 10...으로 이뤄진 문자열을 정수로 바꾼 값
• 순환 소수 :
  비순환부 만 정수로 바꿔놓는다.
  순환부를 포함해서 정수로 바꾼다.
  문자열의 뒷자리부터 순환부의 자릿수만큼 '9'를 빈 문자열에 추가한다.
  그 문자열에 비순환부의 자릿수만큼 '0' 을 추가한다
  그 문자열을 정수형으로 전환한다.
  순환부 정수 - 비순환부 정수 / 9와0으로 이루어진 문자열을 정수로 바꾼 값
• 분모와 분자의 최대공약수를 구해 ( 유클리드 호제법 이용) 기약분수로 바꾼다.

#include <iostream>

using namespace std;

string decimal;
string dnmntr;;

int n, f;
long long up, down, r, nloop;

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    while (n--) {
        dnmntr = "";
        decimal = "";
        nloop = 0;
        cin >> decimal;
        f = (int) decimal.find('(');
        if (f == -1) {
            dnmntr += "1";
            for (int j = 2; j < decimal.size(); j++) {
                dnmntr += "0";
            }
            decimal.erase(0, 2);
            up = stoll(decimal);
        } else {
            for (int j = f + 1; j < decimal.size() - 1; j++) {
                dnmntr += "9";
            }
            for (int j = 2; j < f; j++) {
                dnmntr += "0";
            }
            decimal.erase(0, 2);
            if (f > 2) nloop = stoll(decimal);
            decimal.erase(f - 2, 1);
            up = stoll(decimal) - nloop;
        }
        down = stoll(dnmntr);
        r = gcd(up, down);
        up /= r;
        down /= r;
        cout << up << '/' << down << '\n';

    }
    return 0;
}

느낀 점

• 예전에 수학학원에서 순환 소수를 쉽게 분수로 바꾸는 방법을 배웠던 기억이 있다. 
  그 방법이 분모를 9와0으로 만드는 거였는데 그 논리를 코드로 짜는 과정이 흥미로웠다.
• 어떻게 보면 인간이 이해하기 쉬운 (야매?요령?) 방법인데 문자열로 다루다보니 그 논리르 코드로 짜기도 편한것 같다.

시간복잡도 (테스트 케이스 하나 마다) : O(n)