[BaekJoon] 9734 순환 소수

1.  문제 링크

2.  문제

요약

• 순환 소수가 주어졌을 때, 해당 소수를 분수로 바꾸는 문제입니다. 이 때 분자와 분모는 서로소여야 합니다.
• 입력: 여러 개의 테스트 케이스가 주어지고 각 테스트 케이스에는 순환 소수 하나가 주어집니다. 반복되는 부분은 ()로 표현됩니다.
• 출력: 각 테스트 케이스를 분수로 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public int gcd(int a, int b) {
		if(b == 0) {
			return a;
		} else {
			return gcd(b, a % b);
		}
	}
	
	public String getFraction(String circul_decimals) {
		StringTokenizer st = new StringTokenizer(circul_decimals, ".");
		int num = Integer.parseInt(st.nextToken());
		String next = st.nextToken();
		int first = next.indexOf("(");
		int last = next.indexOf(")") - 1;
		st = new StringTokenizer(next, "()");
		ArrayList<String> nums = new ArrayList<String>();
		while(st.hasMoreTokens()) {
			nums.add(st.nextToken());
		}
		String decimal = num == 0 ? "" : Integer.toString(num);
		int len = decimal.equals("0") ? 0 : decimal.length();
		for(int i = 0; i < nums.size(); i++) {
			decimal += nums.get(i);
		}
		int up = Integer.parseInt(decimal.substring(0, decimal.length())) - (decimal.substring(0, len + first).equals("") ? 0 : Integer.parseInt(decimal.substring(0, len + first)));
		int down = (int)(Math.pow(10, last) - Math.pow(10, first));
		int gcd = gcd(up, down);
		up /= gcd;
		down /= gcd;
		return circul_decimals + " = " + up + " / " + down;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String circul_decimals = "";
		Main m = new Main();
		while((circul_decimals = br.readLine()) != null) {
			bw.write(m.getFraction(circul_decimals) + "\n");
		}
		br.close();
		bw.flush();
		bw.close();
	}
}

4.  접근

• 순환 소수를 분수로 변경하는 방법
1. 주어진 순환 소수를 미지수 하나로 치환합니다. 저는 x라고 하겠습니다.
2. 순환되는 부분 직전까지 소숫점을 이동시킵니다.
3. 순환되는 부분 끝까지 소숫점을 이동시킵니다.
4. 큰 수에서 작은 수를 뺀 후에 x에 대해 나타내면 해당 순환 소수에 대한 분수가 구해집니다.
5. 해당 분수를 약분합니다.
• 예시
1. 주어진 순환소수가 0.25(75)라면 x = 0.25757575...
2. 100x = 25.757575...
3. 10000x = 2575.757575....
4. 10000x = 2575.757575....
   -   100x =     25.757575...
5. 9900x = 2550 -> x = 2550 / 9900 = 17 / 66


• 위의 방법을 코드로 옮겨서 해당 문제를 해결합니다.
• 소숫점 뒤의 수들은 같기 때문에 빼기를 진행하면 사라져 해당 부분을 무시하고 분자와 분모를 따로 구합니다.
• 분자는 주어진 순환 소수를 ()와 .를 지운 하나의 수로 합치고 순환되는 부분 끝까지와 순환되는 부분 직전까지 수를 구한 후에 두 수를 뺍니다.
• 분모는 분자를 구할 때 이용한 두 수에서 각각 원래 위치보다 얼만큼 소숫점을 이동시켰는지를 이용하여 해당 수만큼 10의 거듭제곱을 진행하고 두 수를 뺍니다.
• 분자와 분모가 구해졌으니 두 수의 최대공약수를 찾아 약분을 진행합니다.