#52. [백준_C언어] 1920 : 수 찾기

 

 입력 코드 

#include <stdio.h>

int intcmp(const void *pa, const void *pb) {
	return *(int *)pa > *(int *)pb ? 1 : (*(int *)pa < *(int *)pb ? -1 : 0);
}

int binarySearch(int *arr, int key, int size) { 
	//arr = 배열a[], key = 배열b[i], size = 배열a의 길이 n
	
	int front, mid, rear;
	front = 0; rear = size - 1;

	while (1) {
		mid = (front + rear) / 2;
		if (arr[mid] == key) return 1;
		if (arr[front] == key) return 1;
		if (arr[rear] == key) return 1;

		if (arr[mid] < key) front = mid + 1;
		else rear = mid - 1;
		if (rear <= front) return 0;
	}
}

int main() {
	int i, n, m, a[100000], b[100000];
	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%d", &a[i]);
	qsort(a, n, sizeof(int), intcmp);

	scanf("%d", &m);
	for (i = 0; i < m; i++) {
		scanf("%d", &b[i]);
		b[i] = binarySearch(a, b[i], n);
	}
	for (i = 0; i < m; i++) printf("%d\n", b[i]);
}

 

 

 코드 설명 

#이분 탐색 #정렬

 

이분 탐색을 하려면 정렬이 되어있어야 하는데 정렬을 하려면 또 정렬 알고리즘을 이용해야 한다.

#include <stdio.h>

main() {
	int N, M;
	scanf("%d", &N);
	int arrN[100000], arrM[100000];

	int i, j, key;
	for (i = 0; i < N; i++) {
		scanf("%d", &arrN[i]);
	}

	for (i = 0; i < N-1; i++) {
		j = i;
		while (j >= 0 && arrN[j] > arrN[j + 1]) {
			key = arrN[j];
			arrN[j] = arrN[j + 1];
			arrN[j + 1] = key;
			j--;
		}
	}

	scanf("%d", &M);
	for (j = 0; j < M; j++) {
		scanf("%d", &arrM[j]);
	}

	int left = 0, right = N;

	for (j = 0; j < M; j++) {
		while (left <= right) {
			int mid = (left + right) / 2;

			if (arrN[mid] > arrM[j])
				right = mid - 1;
			else if (arrN[mid] < arrM[j])
				left = mid + 1;
			else if ((arrN[mid] == arrM[j])) {
				printf("1\n");
				break;
			}
			else {
				printf("0\n");
				break;
			}
		}
	}
}

그래서 정렬을 하고 나서 arrM[j]에 대해 이분 탐색을 반복하려고 했으나 중간에 break 할 지점에서 막혔다.

 

2021/01/25 - [C] - #47. [백준_C언어] 2750 : 수 정렬하기

#include <stdio.h>

main() {
	int N, M;
	scanf("%d", &N);
	int arrN[100000], arrM[100000];

	int i, j, key;
	for (i = 0; i < N; i++) {
		scanf("%d", &arrN[i]);
	}

	for (i = 0; i < N - 1; i++) {
		j = i;
		while (j >= 0 && arrN[j] > arrN[j + 1]) {
			key = arrN[j];
			arrN[j] = arrN[j + 1];
			arrN[j + 1] = key;
			j--;
		}
	}

	scanf("%d", &M);
	for (j = 0; j < M; j++) {
		scanf("%d", &arrM[j]);
	}

	int left = 0, right = N, res;

	for (j = 0; j < M; j++) {
		while (left <= right) {
			int mid = (left + right) / 2;

			if (arrN[mid] > arrM[j])
				right = mid - 1;
			else if (arrN[mid] < arrM[j])
				left = mid + 1;
			else if ((arrN[mid] == arrM[j]))
				res = 1;
			else
				res = 0;
		}
		if (res == 1)
			printf("1\n");
		else if (res == 0)
			printf("0\n");
	}
}

새로운 변수 res 를 선언해서 출력을 했으나 시간 초과

그래서 다른 방법을 찾아보다가 퀵 정렬을 이용한 풀이를 발견했다.

 

 

↓↓↓ 참고한 사이트

m.blog.naver.com/occidere/220784779848

[백준] 1920 - 수 찾기

 

 

 이분 탐색 

dongdd.tistory.com/50

이분 탐색 알고리즘(Binary Search Algorithm)

wootool.tistory.com/62

[알고리즘] 이분 탐색

 

 퀵 정렬 

https://terms.naver.com/entry.nhn?cid=51173&categoryId=51173&docId=2270444

퀵 정렬

dojang.io/mod/page/view.php?id=638

C 언어 코딩 도장: 73.2 퀵 정렬 함수 사용하기

 

 

 

 문제 출처 

www.acmicpc.net/problem/1920

1920번: 수 찾기