DevMoon's 살아가는 이야기

이번 문제는 정말 꼼수(?)로 푼것같다 -_-; 한마디로 수학적인 검증? 철학? 이런게 없ㅋ엉ㅋ 

일단 나의 답. 다른 사람들과 비교하니 맞는 것같다.

아래 책에서 나온 문제라는 것!!

문제는 아래와 같다. (새창으로보기)

저 어마어마한 숫자들을 다 저장한다는건 문제를 포기하겠다는 것이고 ..

생각해보니 0이 몇개인지를 카운트 해두고 앞에 몇자리 수만 기억해두면 될 것같았다. 

어차피 곱하기 할 때 앞자리 많은 수들은 0을 만들어내는 것과 관계가 없으므로. 

코드는 아래와 같이.. 짧게 @_@;

#include <stdio.h>

int main()
{
	int N = 0, zeros = 0;
	int mult = 1;

	scanf("%d", &N);

	for(int i=1; i<=N; i++) 
	{
		int div = 10;

		mult *= i;
		while(mult % div == 0) 
		{ 
			div *= 10; 
			zeros++;
		}

		mult /= (div/10);
		mult %= 100000;
	}

	printf("%d %d\n", zeros, mult%10);

	return 0;
}

첫 문제에 이어 두 번째 문제에 도전했다. (책표지 서비스~ 부탁받은대로~ㅋㅋ)

아래 책에 있는 문제라네.

두번째 문제는 개인적으로 너무 어려웠다. 아.. 남은 문제들은 어떻게 푸냐 -_-;;;

규칙을 찾는데 상당히 오래 걸렸는데 그 규칙은 다음과 같다.

이렇게 되는 것이다. 이걸 찾아내는게...참.. 후덜덜..ㅠㅠ

Python, C++, Perl 등 고차원 언어로 짜면 더 간단하게 표현 할 수 있겠지만 난 C로 짰다.

C로 구현하려니 독립적인 집합 표현하기가 힘들었다.

구조체를 이용하다가 코드가 지저분해져서 array의 index를 집합에 들어갈 값으로 하고, 

array 값을 집합 번호로 만들어 구현했다. 덕분에 코드는 좀 깔끔하게 나온듯하다.

#include <stdio.h>

//================================================
// TEST SET
//================================================
const int MAX_N = 16;
const int N = 4;
//================================================

int getMaxGroup(int *array, int size)
{
	int maxGroup = -1;

	for(int i = 0; i < size; i++) {
		if (array[i] > maxGroup) 
			maxGroup = array[i];
	}

	return maxGroup;
}

void printArray(int *array, int size)
{
	int maxGroup = getMaxGroup(array, size);

	for(int i = 0; i <= maxGroup; i++) 
	{
		printf("{");
		for(int j = 0; j < size; j++) {
			if (array[j] == i) {
				printf(" %d ", j);
			}
		}
		printf("}");
	}
	printf("\n");
}

void makeset(int *array, int size, int depth)
{
	if (depth == N) {
		printArray(array, size);
		return ;
	}

	// make new group 
	int maxGroup = getMaxGroup(array, size);

	array[depth] = maxGroup+1;
	makeset(array, size, depth+1);
	array[depth] = -1;

	// attach new element to each group
	for(int i = 0; i <= maxGroup; i++) {
		array[depth] = i;
		makeset(array, size, depth+1);
		array[depth] = -1;
	}
}

int main()
{
	int array[MAX_N];

	// init
	for(int i = 0; i < N; i++) {
		array[i] = -1;
	}

	makeset(array, N, 0);
	return 0;
}

어쨌든 풀어서 기분이 좋군 :)

실행결과

인사이트 에서 재미있는 행사를 하길래 도전해보았다.

문제는 다음과 같다.

구체적인 조건에 대한 언급은 없지만 별도의 메모리는 사용하지 않는게 좋겠다는 생각이 들었다. 

그리고 1만큼 오른쪽으로 이동시키는 과정을 k번 반복해서는 안된다고 하니 O(n)으로 풀기를 원하는구나.

해결전략은 코드와 같다.

#include <stdio.h>

const int MAX_ELEM = 10;

void rotate(int *array, int s, int t, int k)
{
	int range = (t - s + 1);
	int idx = s, cycle = s;
	int insert, save;

	if (k % range == 0) return ;
	if (k > range) k %= range;

	insert = save = array[s];

	for(int i = 0; i < range; i++) 
	{
		insert = save;

		int nextIdx = idx + k;

		// invalid range check
		if (nextIdx > t) {
			nextIdx = (nextIdx % (t+1)) + s;
		}

		save = array[nextIdx];
		array[nextIdx] = insert;

		idx = nextIdx;

		// avoid cycle 
		if (idx == cycle) {
			idx++; cycle++;
			save = array[idx];
		}
	}
}

int main()
{
	int array[MAX_ELEM];

	// make test set
	for(int i = 1; i <= MAX_ELEM; i++) {
		array[i-1] = i;
	}

	rotate(array, 0, 6, 3);

	// print result
	for(int i = 0; i < MAX_ELEM; i++)
		printf("%d ", array[i]);
	printf("\n");

	return 0;
}

간단히 설명하면, 저장될 곳에 있는 값을 변수에 저장해둬서 덮어쓰더라도 값을 보존시켜가는 방식이다.

그 다음 이동은 지금 덮어씌워진 위치에서 시작한다. 현재 덮어쓴 자리에 있던 값은 저장해두었기 때문에 

다음 위치에 저장할 값을 보존할 수 있다. 마찬가지로 다음 위치에 있는 값을 save에 저장하고, 

기존에 있던 값(insert)으로 덮어쓰면 된다. 

이 과정을 범위만큼 반복하면 별도 메모리 필요없이 풀 수 있다.