출처 : 종만북 5.4 다른 기술들 - 순환 소수 찾기
코드설명
순환소수를 찾습니다.
HashMap을 활용하여 소수점에서부터의 숫자, 피연산자인 숫자가 다시 한번 보인다면 해당 숫자는 순환소수입니다.
이에 맞추어서 무한소수 이전부분과 무한소수 이후부분을 나누어서 String을 재조립한뒤 출력하면, 순환소수를 찾을 수 있습니다.
당연히 같은 수로 같은 숫자를 나누면, 무한하게 같은 형태의 나머지가 지속될 것임을 알 수 있습니다. 이러한 부분이 비둘기 집의 원리가 적용되었습니다.
순환소수를 구현하며 아래의 hashmap에 왜 a%b 가 아닌 a를 넣는지 궁금합니다.
이유는, 맨 처음에 밖에서 a = (a%b)*10 으로 들어오고, while문의 마무리도 a = a%b * 10; 으로 마무리되기에 hashmap에도 처음 들어온 a = (a%b)*10 형태로 삽입하여주어야 합니다.
좀 헷갈릴 수 있지만, 생각해보면 알 수 있습니다.
hashmap.put(a, sb.length());
입력 예시 1
3 8결과 예시 1
0.375
입력 예시 2
4712 400결과 예시 2
11.78
입력 예시 3
1 11결과 예시 3
0.(09)입력 예시 4
22 7출력 예시 4
3.(142857)코드
순환소수를 고려한 코드입니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M;
public static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
printDecimal(N, M); // N/M을 실수 연산을 쓰지 않고 이 분수를 소수 형태로 출력하라.
}
public static void printDecimal(int a, int b) {
StringBuilder result = new StringBuilder();
HashMap<Integer, Integer> remainderMap = new HashMap<>();
int integerPart = a / b;
result.append(integerPart);
a = (a % b) * 10;
if (a > 0) {
result.append(".");
}
while (a > 0) {
// 나머지가 이미 등장한 적이 있는지 확인
if (remainderMap.containsKey(a)) {
int start = remainderMap.get(a);
String nonRepeatingPart = result.substring(0, start);
String repeatingPart = result.substring(start);
result = new StringBuilder(nonRepeatingPart + "(" + repeatingPart + ")");
break;
}
remainderMap.put(a, result.length());
result.append(a/b);
a = (a % b) * 10;
}
System.out.println(result.toString());
}
}
순환소수를 고려하지 못한 코드입니다. 1/11 일경우 0.0909090909 ... 가 무한합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M;
public static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
printDecimal(N, M); // N/M을 실수 연산을 쓰지 않고 이 분수를 소수 형태로 출력하라.
}
public static void printDecimal(int a, int b) {
int iter = 0;
// while(a % b != 0) { // 이렇게 처리할경우 while문이 끝나고 한번 더 따로처리해야하여 비효율적입니다.
while(a > 0) {
if(iter++ == 1) System.out.print(".");
System.out.print(a / b);
a = (a % b) * 10;
}
}
}
순환소수 고려하지 않은 코드 2.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M;
public static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
printDecimal(N, M); // N/M을 실수 연산을 쓰지 않고 이 분수를 소수 형태로 출력하라.
}
// 1 11
public static void printDecimal(int a, int b) {
StringBuilder sb = new StringBuilder();
int integerPart = a / b;
sb.append(integerPart);
a = (a % b) * 10;
if( a > 0) { //아직 나머지가 존재한다면, 소수점이 존재한다는 의미입니다.
sb.append(".");
}
while(a > 0) {
sb.append(a/b);
a = (a%b) * 10;
}
System.out.println(sb);
}
}