1920번: 수 찾기

1920번: 수 찾기(BOJ C/C++)

사용 언어: C

문제

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을 출력한다.

 

풀이

문제를 한번 쓱 읽어보면 이중 for문으로 간단하게 풀 수 있을거라고 착각할 수 있지만 이미 백준 문제를 많이 접해본 이상 이렇게 간단히 풀릴 수가 없다. 이중 for문으로 쓰면 시간복잡도는 O(n^2)까지 올라갈 수 있다. 그래서 이분 탐색(이진 탐색)으로 바로 풀 생각을 할 수 있다. 아니면 해시를 사용해서 풀 수도 있겠지만... 아직 해시를 공부한 적이 없기 때문에 언젠가 공부해서 해시 구현 글도 올려보겠다..! 

 

어쨌든 이분 탐색은 시간복잡도가 O(logn)이므로 이중 for문 보다 확실히 빠르고 알아야 할 것이 정렬된 리스트 혹은 배열에서 사용하는 것이므로 입력 받은 배열을 정렬해줘야 한다. 그럼 여기서도 시간복잡도를 따져야하는데 퀵소트가 pivot에 따라 시간복잡도가 최대 O(n^2)일 수 있지만 평균적으로 O(nlogn)이므로 퀵소트를 사용한다. 퀵소트는 그냥 stdlib.h에 있는 qsort 함수를 사용했다.

 

여담으로 밑에 compare(const void *a,~) 에서 const를 붙이는 이유는 이미 고정된 배열 값을 인자로 넘기는데 함수 안에서 이 값을 고의로 혹은 실수로 변경하는 것은 안되서 애초에 컴파일러가 금지하므로 const를 붙여야 오류가 안 뜬다.

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

int compare(const void *a, const void *b)    // 오름차순 비교 함수 구현
{
    int num1 = *(int *)a;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴
    int num2 = *(int *)b;    // void 포인터를 int 포인터로 변환한 뒤 역참조하여 값을 가져옴

    if(num1 < num2) //a가 b보다 작을 때는 -1 반환
        return -1;
    
    if(num1 > num2) //a가 b보다 클 때는 1 반환
        return 1;
    
    return 0; //a와 b가 같을 때는 0 반환
}

int binary_search(int num, int arr[], int low, int high)
{
	int mid;
	while (low <= high)
	{
		mid = (low + high) / 2;
		//탐색 성공
		if (num == arr[mid])
			return 1;
		
		// 탐색 범위 재조정 low ~ mid-1
		else if (num < arr[mid])
			high = mid - 1;
		
		// 탐색 범위 재조정 mid+1 ~ high	
		else if (num > arr[mid])
			low = mid + 1;
	}
	return 0;
}

int main(void)
{
    int low,high,mid;
	int N,M;
	scanf("%d",&N);
	int arr[N];
	for(int i=0;i<N;i++)
		scanf("%d",&arr[i]);
	scanf("%d",&M);
	int data[M];
	for(int i=0;i<M;i++)
		scanf("%d",&data[i]);
	low=0;
	high=N;
	qsort(arr, sizeof(arr)/sizeof(int), sizeof(int),compare);
	for(int i=0;i<M;i++)
		printf("%d\n",binary_search(data[i], arr, low, high));
	
    return 0;
}