[Baekjoon] 4881_자리수의 제곱

문제(출처: https://www.acmicpc.net/problem/4881)

---

< 자리수의 제곱 >

 

문제 풀이 

 

각 숫자의 수열을 구한 후 같은 수가 나올 때까지 필요한 수열의 길이의 합의 최솟값을 구한다.

 

my solution (Java)

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.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class _4881_ { // 자리수의 제곱

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		String a = "", b = "";

		while (!(a = st.nextToken()).equals("0") && !(b = st.nextToken()).equals("0")) {
			bw.write(a + " " + b + " ");

			if (a.equals(b)) {
				bw.write("2\n");
				st = new StringTokenizer(bf.readLine());
				continue;
			}

			ArrayList<String> listA = new ArrayList<>();
			listA.add(a);

			while (true) {
				int sum = 0;
				for (int i = 0; i < a.length(); i++) {
					sum += (a.charAt(i) - '0') * (a.charAt(i) - '0');
				}
				a = Integer.toString(sum);
				if (listA.contains(a)) {
					break;
				}
				listA.add(a);
			}

			int result = 1;
			ArrayList<int[]> list = new ArrayList<>();

			Set<String> set = new HashSet<>();
			set.add(b);

			if (listA.contains(b)) {
				list.add(new int[] { Integer.parseInt(b), result });
			}
			while (true) {
				int sum = 0;
				for (int i = 0; i < b.length(); i++) {
					sum += (b.charAt(i) - '0') * (b.charAt(i) - '0');
				}
				b = Integer.toString(sum);
				result += 1;

				if (set.contains(b)) {
					break;
				}

				if (listA.contains(b)) {
					list.add(new int[] { Integer.parseInt(b), result });
				}

				set.add(b);
			}
			if (list.size() == 0) {
				bw.write("0\n");
			} else {
				result = Integer.MAX_VALUE;
				for (int j = 0; j < list.size(); j++) {
					int temp = list.get(j)[1];
					for (int i = 0; i < listA.size(); i++) {
						temp += 1;
						if (listA.get(i).equals(Integer.toString(list.get(j)[0]))) {
							break;
						}
					}
					result = Math.min(result, temp);
				}
				bw.write(result + "\n");
			}
			st = new StringTokenizer(bf.readLine());
		}
		bw.flush();
	}
}

변수)
a, b : 입력값
listA : a의 수열
sum : 각 자릿수의 제곱의 합
result : b의 수열 순서, 두 수열의 길이의 합의 최솟값
list : a와 b의 같은 수가 나왔을 때의 값과 b 수열 순서
set : b의 반복 사이클 종료 판별을 위한 HashSet

 

a와 b가 0이 아닐 때까지 입력받아 다음 과정을 반복한다.

 

1) a와 b가 같다면 수열의 길이의 합이 2이므로 2 출력 및 다음 입력

2) a의 사이클을 구하기 위해 각 자릿수의 제곱의 합을 구한 후 listA에 존재 여부 확인 후 저장

3) b의 사이클을 구하며 set에 존재 여부 확인 후 존재하면 종료, 존재하지 않는다면 listA에 값이 있는지 확인 후 있다면 list에 같은 수와 수열 순서 저장

4) 만약 list의 크기가 0이라면 같은 수가 나타나지 않는 경우이므로 0 출력

5) list를 순환하면서 listA에서 값의 순서를 찾아 수열의 길이의 합의 최솟값을 구함

6) 최종 result 출력

---

---