[BOJ 백준] 소수를 분수로(5376) C++

링크 : https://www.acmicpc.net/problem/5376

5376번: 소수를 분수로

 

문제 설명 : 

유리수 분수를 소수로 나타내면, 소수점 아래 자리가 유한 개인 경우(1/8 = 0.125)와 어떤 자리에서부터 일정한 숫자가 한없이 되풀이 되는 경우(1/11 = 0.090909...)가 있다.

소수를 입력받은 뒤, 분수로 나타내는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다. 각 테스트 케이스는 한 줄에 소수가 하나씩 주어진다.

소수의 첫 두 자리는 "0."이다. 그 다음에는 숫자 0개~6개가 주어진다. 그 다음, 길이가 1과 9사이면서 괄호로 감싸져있는 수가 주어질 수도 있다. 이 수는 무한히 반복되는 자리를 의미한다.

항상 0이 아닌 자리가 하나는 주어지며, 괄호 안에 주어지는 수는 0이나 9로만 이루어져 있지 않다.

출력 : 

각 테스트 케이스에 대해서, 입력으로 주어진 소수의 분수 표현을 출력한다. (분모와 분자는 서로소이어야 한다)

 

예제 입력 : 

3
0.5
0.(3)
0.6(142857)

예제 출력 : 

1/2
1/3
43/70

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 소수를 분수로 5376
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>

#define MAX (1000000+3)

using namespace std;

long long gcd(long long a, long long b) {
	// 유클리드 호제법
	long long  c;
	while (b) {
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

int tc;	// 테스트케이스 개수
long long gc; //최대 공약수
/*
 순환소수 → 분수 변환과정
  - 분자 : (정수+순환소수 끝까지) - (정수~순환하지 않는 부분까지)
  - 분모 : 순환소수 자리 수만큼 9 / 비순환 소수 자리 수만큼 0
	 ex> 1.2(345) = 12345 - 12 / 9990 = 12333/9990
*/
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d", &tc);

	string inputStr;
	int strLen, pt, noncycleCnt, cycleCnt;

	for (int i = 0; i < tc; i++) {
		// 1. 입력
		cin >> inputStr;

		strLen = inputStr.size();


		// 1. 분자 
		//분자 : (정수 + 순환소수 끝까지) - (정수~순환하지 않는 부분까지)
		long long boonja = 0;

		// "0." 건너뛰고 3번째부터 ~ 순환만 체크
		// pt 분자 포인터
		for (pt = 2; pt < strLen; pt++) {
			if (inputStr[pt] == '(') {
				break;
			}
			boonja = (boonja * 10) + (inputStr[pt] - '0');
		}

		

		// 비순환 자리수 
		noncycleCnt = pt - 2;
		// 순환 자리수
		cycleCnt = 0;

		// '(' 건너뛰고 보겠다
		pt++;
		// 순환있을때 - '('부터
		long long tmp;
		if (pt < strLen) {
			// tmp 비순환 소수
			tmp = boonja;
			for (; inputStr[pt] != ')'; pt++) {
				boonja = (boonja * 10) + (inputStr[pt] - '0');
				cycleCnt++;
			}

			// 전체 - 비순환소수
			if (boonja != tmp) {
				boonja -= tmp;
			}
		}

		// 2. 분모 
		// 분모 : 순환소수 자리 수만큼 9 / 비순환 소수 자리 수만큼 0
		long long boonmo = 0;
		// 1) 순환소수 자리 수만큼 9
		while (cycleCnt--) {
			boonmo = boonmo * 10 + 9;
		}
		if (boonmo == 0) {
			boonmo = 1;
		}

		// 2) 비순환 소수 자리 수만큼 0
		while (noncycleCnt--) {
			boonmo *= 10;
		}

		gc = gcd(boonmo, boonja);
		printf("%lld/%lld\n", (boonja / gc), (boonmo / gc));
	}

	return 0;
}
#endif