Hackerrank | Recursive Digit Sum

Link

https://www.hackerrank.com/challenges/recursive-digit-sum/problem

Problem

Code

이전에 풀었던 SWEA 문제와는 다르게 k라는 변수가 추가됨.
음이 아닌 정수의 자릿수를 더하는 과정을 한 자리 값을 구할때까지 반복하여 얻어낸 한 자리 값을 자릿수근이라고 함.

양의 정수의 자릿수근은 자신보다 작은 수 중 가장 큰 9의 배수에서 몇 번째인지 생각하는 것이 도움이 됨.
ex) 123의 자릿수근 = 123보다 작은 9의 배수 중 가장 큰 117에서 6번째 = 6

자릿수근의 합동공식

와중 여기서는 k라는 변수가 추가됨.
문제에서 sample로 든 9875와 148을 예로 들면

9875의 자릿수근은 2이고
superDigit(9875, 4)의 자릿수근은 8
148의 자릿수근은 4
superDigit(148, 3)의 자릿수근은 3이 나옴.

n의 자릿수근 * k를 한 값의 자릿수근 = superDigit의 값임을 알 수 있음.
문자열을 반복해서 구하는 것이 아니라 더해진 sum값에 k값을 곱하면 자릿수근을 구할 수 있음.

코드를 짜보면
0인 경우는 존재하지 않으므로 넘기고
k가 9의 배수이면 sum값에 곱해지고 이 값을 9로 나눴을 때 나머지가 0이므로
return 9

k가 9의 배수가 아닌 경우
sum값을 구해줌 (n[i]-48을 하면 n[i]를 정수로 변환 가능.)

만약 구한 sum값을 k로 곱한 값을 9로 나눴을 때 나머지가 0이라면
다시 return 0

아니라면 그 나머지를 리턴해줌.

여기서 sum을 int로 지정했을 때,
submit code를 하면 test case 8에서 n에 매우 긴 문자열이 나와
값을 저장할 수 없으므로 자료형을 unsigned long long으로 바꿔줌.

//VS 2019에서는 디버그 중 에러 뜹니다. 본 사이트에서는 잘 돌아갑니다.
#define _CRT_SECURE_NO_WARNINGS
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();
char** split_string(char*);

// Complete the superDigit function below.
// n 문자열 k 반복의 자릿수근 구하기
int superDigit(char* n, int k) {
	if (k % 9 == 0)
		return 9;
	else
	{
		unsigned long long sum = 0;
		for (int i = 0; n[i] != NULL; i++)
			sum += (n[i] - 48);
		if ((sum * k) % 9 == 0)
			return 9;
		else
			return (sum * k) % 9;
	}
}

int main()
{
	FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

	char** nk = split_string(readline());

	char* n = nk[0];

	char* k_endptr;
	char* k_str = nk[1];
	int k = strtol(k_str, &k_endptr, 10);

	if (k_endptr == k_str || *k_endptr != '\0') { exit(EXIT_FAILURE); }

	int result = superDigit(n, k);

	fprintf(fptr, "%d\n", result);

	fclose(fptr);

	return 0;
}

char* readline() {
	size_t alloc_length = 1024;
	size_t data_length = 0;
	char* data = malloc(alloc_length);

	while (true) {
		char* cursor = data + data_length;
		char* line = fgets(cursor, alloc_length - data_length, stdin);

		if (!line) {
			break;
		}

		data_length += strlen(cursor);

		if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') {
			break;
		}

		alloc_length <<= 1;

		data = realloc(data, alloc_length);

		if (!line) {
			break;
		}
	}

	if (data[data_length - 1] == '\n') {
		data[data_length - 1] = '\0';

		data = realloc(data, data_length);
	}
	else {
		data = realloc(data, data_length + 1);

		data[data_length] = '\0';
	}

	return data;
}

char** split_string(char* str) {
	char** splits = NULL;
	char* token = strtok(str, " ");

	int spaces = 0;

	while (token) {
		splits = realloc(splits, sizeof(char*) * ++spaces);

		if (!splits) {
			return splits;
		}

		splits[spaces - 1] = token;

		token = strtok(NULL, " ");
	}

	return splits;
}

Result