[사전] 이진탐색 응용, 단일모드 배열

문제 1: 정렬되어 있는 n개의 정수 키(사전)와 탐색할 키 k1, k2를 입력받아, 사전에서 k1 ≤ k ≤ k2 를 만족하는 위치들을 출력하는 프로그램을 작성

 

- 재귀 버전 구현

 

입력 예시 1
8 –7 15 ↦ n=8, k1=–7, k2=15
-92 -31 -7 4 14 20 29 44

출력 예시 1
□2 3 4 ↦ 사전에서 -7의 위치는 2, 15보다 작으면서 가장 큰 위치는 4

입력 예시 2
8 33 40 ↦ n=8, k1=33, k2=40
-92 -31 -7 4 14 20 29 44

출력 예시 2
□-1 ↦ 문제 조건을 만족하는 사전의 키 없음

 

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

int t1 = 0;
int t2 = NULL;

int rFE(int k, int left, int right, int X[]) {
	int mid;

	if (left > right)
		return -1;

	mid = (left + right) / 2;
	if (k == X[mid])
		return mid;
	else if (k < X[mid]) {
		t1 = mid;
		return rFE(k, left, mid - 1, X);
	}
	else {
		t2 = mid;
		return rFE(k, mid + 1, right, X);
	}
}

int findElement(int k, int n, int X[]) {
	return rFE(k, 0, n - 1, X);
}

int main() {
	int n, k1, k2;
	int* X;
	int a, b;

	scanf("%d %d %d", &n, &k1, &k2);

	X = (int*)malloc(n * sizeof(int));

	for (int i = 0; i < n; i++) {
		scanf("%d", &X[i]);
	}

	a = findElement(k1, n, X);
	if (a == -1) {
		if (t1 != 0)
			a = t1;
	}

	b = findElement(k2, n, X);
	if (b == -1) {
		if (t2 != NULL)
			b = t2;
	}

	if ((a != -1 && b != -1) && (a <= b)) {
		for (int i = a; i <= b; i++) {
			printf(" %d", i);
		}
	}
	else
		printf(" -1");

	free(X);

	return 0;
}

* rFE함수에서 재귀 방식으로 구현하니까 return rFE(~~~) 해야함.

** x[mid] 값이랑 비교할 때 x배열 안에 mid 넣는거 잊지않기!!!!!!!!!!!!!

 

 

문제 2: 해당 배열이 단일모드 배열인지 확인 & 해당 배열의 최대 키 혹은 최소 키를 출력

 

- 크기가 n인 배열을 동적 할당하여, 입력된 사전의 키 저장(중복 키는 없다고 가정)
- 해당 배열이 단일모드인지 확인 (증가→감소 / 감소→증가)
- 이진탐색과 유사한 형태로 해당 배열의 최대 키 혹은 최소 키 출력 – O(log n) 시간 필요

 

입력 예시 1
9 ↦ n=9
-21 8 12 13 35 41 23 20 17

출력 예시 1
□1 41 ↦ 증가→감소 단일모드 1 / 최대값 41

입력 예시 2
9 ↦ n=9
-21 8 12 13 -1 41 23 20 17

출력 예시 2
□0 ↦ 단일모드 배열 아님 0

 

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

// 단일모드

int check(int *x, int n) {
	int flag = 0;
	int t1 = 0, t2 = 0;// 갯수 체크
	for (int i = 0; i < n-1; i++) {
		if (x[i] < x[i + 1]) {
			flag = 1;
			t1++;
		}
		else if (flag == 1) {
			for (int j = i; j < n-1; j++) {
				if (x[j] > x[j + 1]) {
					t1++;
					flag = 2;
					i++;
				}
			}
		}
		if (t1 == n-1) {
			flag = 1;
			break;
		}
		else if (flag == 2) {
			break;
		}
	}

	if (t1 != n - 1 && (flag == 1 || flag == 0)) {
		for (int i = 0; i < n - 1; i++) {
			if (x[i] > x[i + 1]) {
				flag = -1;
					t2++;
			}
			else if (flag == -1) {
				for (int j = i; j < n - 1; j++) {
					if (x[j] < x[j + 1]) {
						t2++;
						flag = 2;
						i++;
					}
				}
			}
			if (t2 == n - 1) {
				flag = -1;
				break;
			}
			else if (flag == 2) {
				break;
			}
		}
	}

	return flag;
}

int findMaxOfUnimodalArray(int* x, int n) {
	int a = 0;
	int b = n - 1;
	int mid;

	while (a < b) {
		mid = (a + b) / 2;

		if (x[mid] < x[mid + 1])
			a = mid + 1;
		if (x[mid] > x[mid + 1])
			b = mid;
	}

	return x[a];
}

int findMinOfUnimodalArray(int* x, int n) {
	int a = 0;
	int b = n - 1;
	int mid;

	while (a < b) {
		mid = (a + b) / 2;

		if (x[mid] > x[mid + 1])
			a = mid + 1;
		if (x[mid] < x[mid + 1])
			b = mid;
	}

	return x[a];
}

int main() {
	int n, * x;
	int chk, r;

	scanf("%d", &n);

	x = (int*)malloc(sizeof(int) * n);
	if (x == NULL) {
		printf("Not enough memory!");
		return -1;
	}

	for (int i = 0; i < n; i++) {
		scanf("%d", &x[i]);
	}

	//단일모드 확인
	chk = check(x, n);
	
	if (chk == 1) {//단일모드 증->감
		r = findMaxOfUnimodalArray(x, n);
		printf(" %d %d", chk, r);
	}
	else if (chk == -1) {//단일모드 감->증
		r = findMinOfUnimodalArray(x, n);
		printf(" %d %d", chk, r);
	}
	else {// 단일모드 ㄴㄴ
		printf(" 0");
	}

	free(x);

	return 0;
}