[BaekJoon] 5376 소수를 분수로

1.  문제 링크

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

2.  문제

요약

• 주어진 순환소수에 대하여 그 수에 해당하는 분수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 테스트 케이스의 개수가 주어지고 두 번째 줄부터 테스트 케이스 개수만큼 순환소수가 주어집니다.
  - 순환소수는 첫 두자리는 "0."이고 그 다음부터 0개 이상 6개 이하의 숫자가 주어집니다. 그 이후 길이가 1에서 9 사이면서 괄호로 감싸져있는 순환되는 수가 주어집니다.
• 출력: 각 테스트 케이스에 대한 분수를 출력합니다.

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.LinkedHashMap;

public class Main {
	public long gcd(long a, long b) {
		if(b == 0) {
			return a;
		}
		return gcd(b, a % b);
	}
	
	public String[] getFraction(String[] nums) {
		String[] fraction = new String[nums.length];
		for(int i = 0; i < nums.length; i++) {
			if(!nums[i].contains("(")) {
				int denominator = (int)Math.pow(10, nums[i].length() - 2);
				int numerator = Integer.parseInt(nums[i].substring(2, nums[i].length()));
				long gcd_num = gcd(denominator, numerator);
				fraction[i] = Long.toString(numerator / gcd_num) + "/" + Long.toString(denominator / gcd_num);
			} else {
				int index = nums[i].indexOf("(");
				int len = nums[i].length() - 2;
				long denominator = (long)Math.pow(10, len - 2) - (long)Math.pow(10, index - 2);
				String numerator_str = nums[i].substring(2, nums[i].length() - 1);
				numerator_str = numerator_str.replace("(", "");
				numerator_str = numerator_str.replace(")", "");
				long numerator = Long.parseLong(numerator_str);
				if(!nums[i].substring(2, index).equals("")) {
					numerator -= Long.parseLong(nums[i].substring(2, index));
				}
				long gcd_num = gcd(denominator, numerator);
				fraction[i] = Long.toString(numerator / gcd_num) + "/" + Long.toString(denominator / gcd_num);
			}
		}
		return fraction;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int test_num = Integer.parseInt(br.readLine());
		String[] nums = new String[test_num];
		for(int i = 0; i < nums.length; i++) {
			nums[i] = br.readLine();
		}
		br.close();
		Main m = new Main();
		String[] fraction = m.getFraction(nums);
		for(String f : fraction) {
			bw.write(f + "\n");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 순환소수를 분수로 변환하는 방법을 이용해야 합니다. 해당 방법은 이전에 게시했던 순환소수 문제에 게시하였습니다.

  https://velog.io/@taeho97/BaekJoon-9734-%EC%88%9C%ED%99%98-%EC%86%8C%EC%88%98

• 순환소수를 분수로 변환하는 방법
  1. 순환되는 부분 이전까지 소숫점을 이동하며 10의 거듭제곱을 곱해줍니다.
  2. 순환되는 부분 끝까지 소숫점을 이동하며 10의 거듭제곱을 곱해줍니다.
  3. 2번에서 구한 수와 1번에서 구한 수를 빼주고 2번에서 10을 거듭제곱해준 수와 1번에서 10을 거듭제곱해준 수를 빼준 후, 전자를 분자, 후자를 분모로 하여 약분합니다.
• 위 방법을 이용해여 해당 문제를 해결해갑니다.

1. 주어진 수가 순환소수인지 유한소수인지 괄호의 유무로 판단합니다.
2. 만약 유한소수라면 소숫점이 해당 소수의 끝까지 이동하도록 10의 거듭제곱을 곱해주고 10의 거듭제곱 수를 분모로, 거듭제곱을 곱해준 수를 분자로 하여 두 수를 약분합니다.
   • 약분을 진행할 때는 두 수의 최대공약수를 찾아 두 수를 최대공약수로 나눠줍니다.
3. 만약 순환소수라면 순환되는 부분 끝까지 소숫점이 이동할만큼의 10의 거듭제곱 수에서 순환되는 부분 바로 앞까지 소숫점이 이동할만큼의 10의 거듭제곱 수를 빼준 수를 분모로, 순환되는 부분 끝까지의 수에서 순환되는 부분 바로 앞까지의 수를 빼준 수를 분자로 하여 약분합니다.
4. 위 방법으로 구한 분수를 출력합니다.