<C언어 알고리즘> 배열의 인덱스와 값이 일치하는 경우 찾기

입력으로 주어지는 배열 A[0..n-1]은 오름차순으로 정렬되어 있으며 n 개의 서로 다른 정수들을 원소로 가진다. 즉, A[0] < A[1] < … < A[n-1] 이다. 원소들은 양수, 음수 혹은 0일 수 있다.

(a) A[i]=i를 만족하는 index i가 존재하는지 알고 싶다. 그런 index i가 존재하면 찾아서 i를 출력하고, 없으면 -1을 출력하는 알고리즘을 설계하시오.

(b) 배열 A의 원소들이 모두 0 혹은 양수라는 조건이 성립한다면, 위의 문제를 해결하는 더 빠른 알고리즘이 가능하다. 어떻게 할 수 있을까?

---

Solution

(a)

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void value_equals_index(int *arr,int current,int size,int count)
{
	if(current>=size || arr[current]>current)
	{
		if(count==0)
			printf("-1");
		printf("\n");
		return;
	}
	else if(arr[current]==current)
	{
		printf("%d ", current);
		value_equals_index(arr,current+1,size,count+1);
	}
	else
		value_equals_index(arr,current+1,size,count);
}

int main(void)
{
	int size, *arr=NULL;
	srand((unsigned)time(NULL));

	printf("size: ");
	scanf("%d", &size);
	arr=(int *)malloc(size*sizeof(int));

	for(int i=0;i<size;i++)
	{
		int flag=0;

		do
		{
			flag=0;
			arr[i]=rand()%100-50;

			for(int j=0;j<i;j++)
				if(arr[i]==arr[j])
				{
					flag=1;
					break;
				}
		}
		while(flag);
	}

	for(int i=0;i<size-1;i++)
		for(int j=i+1;j<size;j++)
			if(arr[i]>arr[j])
			{
				int temp=arr[i];
				arr[i]=arr[j];
				arr[j]=temp;
			}

	printf("sorted array: ");
	for(int i=0;i<size;i++)
		printf("%d ", arr[i]);
	printf("\n");

	value_equals_index(arr,0,size,0);

	free(arr);
	return 0;
}

 

(b)

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void value_equals_index(int *arr,int current,int size,int count)
{
	if(current>=size || arr[current]!=current)	//이 부분이 바뀜: >에서 !=으로 -> 더 빠른 종료조건
	{
		if(count==0)
			printf("-1");
		printf("\n");
		return;
	}
	else if(arr[current]==current)
	{
		printf("%d ", current);
		value_equals_index(arr,current+1,size,count+1);
	}
	else
		value_equals_index(arr,current+1,size,count);
}

int main(void)
{
	int size, *arr=NULL;
	srand((unsigned)time(NULL));

	printf("size: ");
	scanf("%d", &size);
	arr=(int *)malloc(size*sizeof(int));

	for(int i=0;i<size;i++)
	{
		int flag=0;

		do
		{
			flag=0;
			arr[i]=rand()%100;

			for(int j=0;j<i;j++)
				if(arr[i]==arr[j])
				{
					flag=1;
					break;
				}
		}
		while(flag);
	}

	for(int i=0;i<size-1;i++)
		for(int j=i+1;j<size;j++)
			if(arr[i]>arr[j])
			{
				int temp=arr[i];
				arr[i]=arr[j];
				arr[j]=temp;
			}

	printf("sorted array: ");
	for(int i=0;i<size;i++)
		printf("%d ", arr[i]);
	printf("\n");

	value_equals_index(arr,0,size,0);

	free(arr);
	return 0;
}