[백준 C언어] 1920. 수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 나의 풀이

#include <stdio.h>
#include <stdlib.h>
 
int cmp(const int* a, const int* b) { //qsort의 매개변수용 compare 함수
	return *(int*)a > *(int*)b;
}
 
int main(void) {
	int n, m, s;
	scanf("%d", &n);
	int arr[100000];
	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);
 
	qsort(arr, n, sizeof(int), cmp);
 
	scanf("%d", &m);
 
	for (int i = 0; i < m; i++) {
		scanf("%d", &s);	
		int mid, left = 0, right = n - 1;
		int flag = 0;
		while (right >= left) {
			mid = (left + right) / 2;
			if (s == arr[mid]){
                		flag = 1;
                		break;
            		}
			if (s < arr[mid]) right = mid - 1;
			else left = mid + 1;
		}
		printf("%d\n", flag);
	}
	return 0;
}

 

 

시간 제한 1초라는 제약 조건이 걸려 있는 문제이다. 

이 문제에서 순차 검색을 사용할 때, 최악의 경우에는 100,000*100,000번+a를 탐색해야 하므로 

십중팔구 제출 시 시간 초과를 목격하게 될 것이다... 

빠르고 간단한 이진 검색 등 다른 방법을 사용하는 것이 좋다. 

나는 이진 검색을 사용했다. 

 

이진 검색이란, 정렬되어 있는 배열에서 값을 검색하는 검색 방법이다. 

찾아야 하는 값 key와 배열의 중앙값을 비교한 후,

key보다 배열의 중앙값이 작으면 중앙값 기준 오른쪽 범위(mid+1~right)부터,

key보다 배열의 중앙값이 크면 중앙값 기준 왼쪽 범위(left~mid-1)부터 동일한 방법으로 검색한다.

int bin_search(int arr[], int n, int s) { //arr : 검색 대상 배열, n : 배열의 요소 수, s : 검색값
	int mid, left = 0, right = n - 1; //검색범위 지정. left : 배열의 왼쪽 끝, right : 배열의 오른쪽 끝
	while (right >= left) {
		mid = (left + right) / 2; //mid : 범위의 중앙값
		if (s == arr[mid]) return mid; //검색대상값과 중앙값이 일치할 경우 인덱스 리턴
		if (s < arr[mid]) right = mid - 1; //중앙값보다 검색값이 작을 경우 right를 mid-1로 바꾸기
		else left = mid + 1; //중앙값보다 검색값이 클 경우 left를 mid+1로 바꾸기
	}
	return 0;
}

 

위와 같이 값을 기준으로  배열의 범위를 1/2로 좁히면서 검색하기 때문에

검색 대상이 되는 배열은 무조건 정렬이 되어 있어야 한다.

 

위 코드에서는 시간을 줄이기 위해 qsort를 활용해 첫 번째 배열을 정렬하고, 

값을 받아온 후 이진 검색을 하게 된다.

범위를 줄여가며 값이 검색되었다면 플래그 변수를 1로 만들어준 후 출력, 

더 이상 줄일 수 없을 때까지 줄였는데 값이 검색되지 않았다면 플래그 변수를 그대로 출력한다.

 

 

(풀어보기 : https://www.acmicpc.net/problem/1920)