반복수열

문제

언어

  • JavaScript

순서도

  1. 규칙에 맞춰서 수열의 다음 수를 만들어가며, 방문 처리를 해줍니다.
  2. 만약 만든 다음 수가 이미 방문 처리된 숫자라면 반복 멈추기
  3. 만든 수열에서 중복된 수들을 제거하고, 개수 세서 출력하기

문제 풀이 step 1

  • 다음과 같이 정의된 수열이 있습니다.
    • D[1] = A
    • D[n] = D[n - 1] 의 각 자리 숫자를 P 번 곱한 수들의 합
  • 예를 들어, A = 14, P = 3 이면,
    • D[1] = 14
    • D[2] = 1 x 1 x 1 + 4 x 4 x 4 = 65
  • 위의 방식처럼 수열을 계속 구하다 보면 언젠가 반복수열이 생깁니다. 이 때, 반복되는 부분을 모두 제외했을 때, 수열에 남게되는 수들의 개수를 구하는 문제입니다.

문제 풀이 step 2

  • A와 P가 주어집니다.
  • 우선, D[1] = A 입니다.
  • D[2] = A 의 각 자리의 숫자를 P 번 제곱한 수들의 합입니다.
  • 매번 다음 수열을 구할 때마다 “BFS 에서의 방문처리” 처럼 방문처리를 해줍니다.
  • 이렇게 계속해서 다음 수열을 구해나가다가 다음 수열이 이미 방문처리된 수열이라면, 반복을 멈춥니다.
  • 그리고 여태까지 구한 수열에서 맨 처음부터 순회해가면서, 반복이 시작되는 부분 이전까지의 숫자들의 개수를 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	let [a, p] = input[0].split(" ");
	[a, p] = [a.split("").map(Number), Number(p)];

	let nextNum = null;
	const isExist = []; // 방문처리를 하기 위한 배열
	isExist[a.join("")] = true; // A 를 방문 처리
	const nums = [a.join("")];
	while (true) {
		// 수열의 각 자리 수를 P 번 제곱한 수들을 더하는 방식을 통해서 다음 수열 구하기
		nextNum = a.map((num) => Math.pow(num, p)).reduce((ac, v) => ac + v);

		// 다음 수열이 이미 방문처리된 수라면 반복 멈추기
		if (isExist[nextNum]) break;

		a = String(nextNum).split("").map(Number);
		isExist[nextNum] = true; // 다음 수열을 방문 처리
		nums.push(nextNum);
	}

	let res = 0;
	// 여태까지 만든 수열들 순회하며 반복이 시작되는 부분 찾기
	for (let i = 0; i < nums.length; i++) {
		if (nums[i] === nextNum) {
			res = i;
			break;
		}
	}

	return res;
};

console.log(solution(input));